maze - dfs

走迷宫可以用dfs或者dfs来做，当求最小路径的时候用bfs最方便。这里使用bfs来找迷宫的最短路径。做法就是先用bfs记录走到终点的过程中每一格的步数，这样从终点往回走就能走到最小路径。

输入的迷宫文件maze_file.in，0代表可以走的路：

6 5

0 1 0 0 0

0 0 0 1 0
0 1 1 1 0
1 1 0 0 0
0 1 0 1 1
0 1 0 0 0

代码：

go:

package main

import (
	"fmt"
	"os"
)

type point struct {
	i, j int
	val  int
}

func (p point) add(next point) point {
	return point{i: p.i + next.i, j: p.j + next.j}
}

// 判断点是否出界
func (p point) at(grid [][]int) (int, bool) {
	if p.i < 0 || p.i >= len(grid) || p.j < 0 || p.j >= len(grid[0]) {
		return 0, false
	}
	return grid[p.i][p.j], true
}

var dirs = []point{{i: -1, j: 0}, {i: 1, j: 0}, {i: 0, j: -1}, {i: 0, j: 1}}

func walk(maze [][]int, start, end point) [][]int {
	var steps = make([][]int, len(maze)) // 记录走到当前位置的最小步数
	for i := range steps {
		steps[i] = make([]int, len(maze[0]))
	}

	queue := []point{start}

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]

		if cur == end {
			break
		}

		for _, dir := range dirs {
			next := cur.add(dir)

			if val, ok := next.at(maze); !ok || val == 1 {
				continue
			}

			if val, ok := next.at(steps); !ok || val != 0 {
				continue
			}

			if next == start {
				continue
			}

			curSteps, _ := cur.at(steps)
			steps[next.i][next.j] = curSteps + 1
			queue = append(queue, 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)

	var maze = make([][]int, row)
	for i := range maze {
		maze[i] = make([]int, col)
		for j := range maze[i] {
			_, _ = fmt.Fscan(file, &maze[i][j])
		}
	}

	return maze
}

func main() {
	maze := readMaze("./maze_file.in")
	start := point{i: 0, j: 0}
	end := point{i: len(maze), j: len(maze[0])}

	steps := walk(maze, start, end)

	var res = make([][]int, len(maze)) // 记录走到当前位置的最小步数
	for i := range steps {
		res[i] = make([]int, len(maze[0]))
	}

	i := end.i - 1
	j := end.j - 1
	res[i][j] = 1
	for !(i == start.i && j == start.j) {
		for _, dir := range dirs {
			nextI, nextJ := dir.i+i, dir.j+j
			if nextI < 0 || nextI >= len(steps) || nextJ < 0 || nextJ >= len((steps)[0]) {
				continue
			}
			if steps[nextI][nextJ] == steps[i][j]-1 {
				i, j = nextI, nextJ
				res[nextI][nextJ] = 1
				break
			}
		}
	}

	for _, row := range res {
		for _, val := range row {
			fmt.Printf("%3d", val)
		}
		fmt.Println()
	}

}