Google资深工程师深度讲解Go语言-迷宫的广度优先搜索(十二)

举报
lxw1844912514 发表于 2022/03/27 00:26:18 2022/03/27
【摘要】 一.广度优先算法 为爬虫实战项目做好准备应用广泛,综合性强面试常见 探索顺序: 上左下右 节点三种状态: 已经发现,但没有探索过 已经发现,并探索完成没有发现 结束条件:(1)走到终点  (2)走到队列为空 maze.go读取文件 package main import ( "fmt" "os") func...

一.广度优先算法

  • 为爬虫实战项目做好准备
  • 应用广泛,综合性强
  • 面试常见

探索顺序: 上左下右

节点三种状态:

  1. 已经发现,但没有探索过 
  2. 已经发现,并探索完成
  3. 没有发现

结束条件:(1)走到终点  (2)走到队列为空

maze.go读取文件


      package main
      import (
     	"fmt"
     	"os"
      )
      func readMaze(filename string) [][]int {
      	file, err := os.Open(filename)
     	if err != nil {
     		panic(err)
      	}
     	var row, col  int
      	fmt.Fscanf(file, "%d %d", &row, &col)
      	maze := make([][]int, row)
     	for i := range maze {
      		maze[i] = make([]int, col)
     		for j := range maze[i] {
      			fmt.Fscanf(file, "%d", &maze[i][j])
      		}
      	}
     	return maze
      }
      func main() {
      	maze:=readMaze("maze/maze.in")
     	for _,row:= range maze{
     		for _,val:=range row {
      			fmt.Printf("%d ",val)
      		}
      		fmt.Println()
      	}
      }
  
 

maze.in文件


      6 5
      0 1 0 0 0
      0 0 0 1 0
      0 1 0 1 0
      1 1 1 0 0
      0 1 0 0 1
      0 1 0 0 0
  
 

广度优先算法代码


      package main
      import (
     	"fmt"
     	"os"
      )
      type point struct {
      	i, j int
      }
      var dirs = [4]point{
      	{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
      func (p point) add(r point) point {
     	return point{p.i + r.i, p.j + r.j}
      }
      func (p point) at(grid [][]int) (int, bool) {
     	if p.i < 0 || p.i >= len(grid) {
     		return 0, false
      	}
     	if p.j < 0 || p.j >= len(grid[p.i]) {
     		return 0, false
      	}
     	return grid[p.i][p.j], true
      }
      func walk(maze [][]int, start, end point)[][]int {
      	steps := make([][]int, len(maze))
     	for i := range steps {
      		steps[i] = make([]int, len(maze[i]))
      	}
     	//队列
      	Q := []point{start}
     	for len(Q) > 0 {
      		cur := Q[0]
      		Q = Q[1:]
     		if cur==end {
     			break
      		}
     		for _, dir := range dirs {
      			next := cur.add(dir)
     			//maze at next is 0
     			//and steps at next is 0
     			//and next !=start
      			val, ok := next.at(maze)
     			if !ok || val == 1 {
     				continue
      			}
      			val, ok = next.at(steps)
     			if !ok || val != 0 {
     				continue
      			}
     			if next == start {
     				continue
      			}
      			curSteps, _ := cur.at(steps)
      			steps[next.i][next.j] = curSteps + 1
      			Q = append(Q, next)
      		}
      	}
     	return steps
      }
      func readMaze(filename string) [][]int {
      	file, err := os.Open(filename)
     	if err != nil {
     		panic(err)
      	}
     	var row, col int
      	fmt.Fscanf(file, "%d %d", &row, &col)
      	maze := make([][]int, row)
     	for i := range maze {
      		maze[i] = make([]int, col)
     		for j := range maze[i] {
      			fmt.Fscanf(file, "%d", &maze[i][j])
      		}
      	}
     	return maze
      }
      func main() {
      	maze := readMaze("maze/maze.in")
     	/*for _, row := range maze {
       for _, val := range row {
       fmt.Printf("%d ", val)
       }
       fmt.Println()
       }*/
      	steps:=walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
     	for _,row:=range steps {
     		for _,val:=range row{
      			fmt.Printf("%3d",val)
      		}
      		fmt.Println()
      	}
      }
  
 

结果:

总结

  • 用循环创建二维slice
  • 使用slice来实现队列
  • 用Fscanf读取文件
  • 对point的抽象

 

文章来源: blog.csdn.net,作者:lxw1844912514,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/lxw1844912514/article/details/108586572

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。