迷宫搜索算法

```go 迷宫数据文件 maze.in 12 16 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 搜索程序： package main import ( "fmt" "log" "os" "strconv" ) 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 } //只适配linux格式文本,windows文本格式显示有问题。 func readMaze(filename string) [][]int { var row, col int file, err := os.Open(filename) if err != nil { panic(err) } defer file.Close() fmt.Fscanf(file, "%d %d", &row, &col) fmt.Println(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]) } fmt.Println() } return maze } //广度优先搜索 func walk(maze [][]int, start, end point) map[string]int { steps := make([][]int, len(maze)) for i := range steps { steps[i] = make([]int, len(maze[i])) } Q := []point{start} log.Print(Q) var cur point 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.i][next.j] = curSteps - 1 Q = append(Q, next) } } //生成path列表 //fmt.Println(start, end, cur, steps[cur.i][cur.j]) path := getPath(steps, cur) return path } func getPath(steps [][]int, cur point) map[string]int { path := make(map[string]int) num := steps[cur.i][cur.j] for num < 1 { path[strconv.Itoa(cur.i)+","+strconv.Itoa(cur.j)] = num num++ for _, dir := range dirs { next := cur.add(dir) val, ok := next.at(steps) if ok && val == num { cur = next break } } } return path } func main() { maze := readMaze("maze.in") path := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1}) for i := 0; i < len(maze); i++ { for j := 0; j < len(maze[0]); j++ { if _, ok := path[strconv.Itoa(i)+","+strconv.Itoa(j)]; ok { fmt.Printf("%s ", "@") } else { fmt.Printf("%d ", maze[i][j]) } } fmt.Println() } } 执行结果： @ 1 @ @ @ 1 0 1 0 1 1 1 1 1 1 1 @ @ @ 1 @ 1 @ @ @ @ @ @ @ @ @ @ 0 1 0 1 @ 1 @ 0 1 1 1 1 1 1 0 @ 1 1 1 @ @ 1 @ 1 1 0 @ @ @ @ 1 @ 0 1 @ @ 1 1 @ 1 1 1 @ 1 1 @ @ @ 0 1 @ 0 0 1 @ 1 1 0 @ 0 0 1 1 1 1 @ @ 1 1 1 @ 1 0 0 @ 0 0 0 0 0 0 @ 1 0 0 1 @ @ 1 1 @ 1 1 1 1 0 1 @ 0 1 0 1 1 @ 1 @ @ 0 0 0 0 0 0 @ 1 0 1 1 @ @ 1 @ 1 1 1 1 1 1 1 @ @ 1 @ @ @ 1 0 @ @ @ 1 @ @ @ 1 1 @ @ @ 1 0 1 0 0 0 @ @ @ 1 @ ```