Google资深工程师深度讲解Go语言-迷宫的广度优先搜索(十二)
【摘要】
一.广度优先算法
为爬虫实战项目做好准备应用广泛,综合性强面试常见
探索顺序: 上左下右
节点三种状态:
已经发现,但没有探索过 已经发现,并探索完成没有发现
结束条件:(1)走到终点 (2)走到队列为空
maze.go读取文件
package main import ( "fmt" "os") func...
一.广度优先算法
- 为爬虫实战项目做好准备
- 应用广泛,综合性强
- 面试常见
探索顺序: 上左下右
节点三种状态:
- 已经发现,但没有探索过
- 已经发现,并探索完成
- 没有发现
结束条件:(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）