广度优先算法
package main
import (
"fmt"
"os"
)
func readMaze( filename string ) [][]int {
file ,err := os.Open(filename)
if err != nil {
panic(err)
}
var row,col ,z int
fmt.Fscanf(file,"%d %d %d", &row,&col,&z)
fmt.Printf("%d , %d, %d ",row,col,z)
fmt.Println()
// [][]int ,第一个方括号是一个slice ,第二个方括号是slice 里的元素
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
}
// 当前点位
type point struct {
x,y int
}
//起始点四个方向坐标 上,左,下,右
var dirs = [4]point{
{-1,0},{0,-1},{1,0},{0,1},
}
//计算下一个点
func (p point) add(r point) point {
return point{p.x+r.x,p.y+r.y}
}
// 检查当前点是否越界
func (p point) at(grid [][]int ) (int, bool) {
if p.x < 0 || p.x >= len(grid) {
return 0 ,false
}
if p.y < 0 || p.y >= len(grid[p.x]) {
return 0 ,false
}
return grid[p.x][p.y],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)
// 验证当前点位在迷宫中是否可以继续走
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.x][next.y] = curSteps+1
Q = append(Q,next)
}
}
return steps
}
func main() {
maze := readMaze("maze/maze.in")
/*for _,row := range maze {
for _, val := range row {
fmt.Printf(" %3d", 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()
}
}
迷宫数据
6 8
0 1 0 0 0 1 0 0
0 0 0 1 0 1 0 0
0 1 0 1 0 0 1 0
1 1 1 0 0 1 0 0
0 1 0 0 1 1 0 1
0 1 0 0 0 0 0 0
计算结果
0 0 4 5 6 0 0 0
1 2 3 0 7 0 0 0
2 0 4 0 8 9 0 0
0 0 0 10 9 0 17 0
0 0 12 11 0 0 16 0
0 0 13 12 13 14 15 16