大家好，又见面了，我是全栈君。
一.广度优先算法
- 为爬虫实战项目做好准备
- 应用广泛,综合性强
- 面试常见
探索顺序: 上左下右
节点三种状态:
- 已经发现,但没有探索过
- 已经发现,并探索完成
- 没有发现
结束条件:(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的抽象
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/111688.html原文链接：https://javaforall.net
