迷宫搜索

递归与回溯

说明

沿可走的邻格探索并标记访问；找到目标后返回路径。

分析

从起点出发检查上下左右四个邻格，只进入边界内、可通行且未访问的位置。path 随递归前进而追加，失败回退时删除最后一个位置；成功时保留整条路径。

图解推演

正文 2×2 网格中，右上角不可通行，路径只能先下再右。seen 表示已搜索过的位置，path 只表示当前递归链；失败时只弹出 path。对静态迷宫的可达性搜索，这种全局访问标记足够；若要枚举所有简单路径，则需另一套回溯访问规则。

查看图表代码

适用前提与边界

DFS 找到的是一条路径，不保证步数最短，最短路应使用 BFS。

示例输入与调用

grid := [][]bool{{true, false}, {true, true}}
	fmt.Println(MazePath(grid, [2]int{0, 0}, [2]int{1, 1}))

运行输出

[[0 0] [1 0] [1 1]]

完整 Go 示例

package main

import "fmt"

func MazePath(grid [][]bool, start, goal [2]int) [][2]int {
	seen := make([][]bool, len(grid))
	for i := range grid {
		seen[i] = make([]bool, len(grid[i]))
	}
	path := [][2]int{}
	dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	var dfs func(int, int) bool
	dfs = func(r, c int) bool {
		if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[r]) || !grid[r][c] || seen[r][c] {
			return false
		}
		seen[r][c] = true
		path = append(path, [2]int{r, c})
		if [2]int{r, c} == goal {
			return true
		}
		for _, d := range dirs {
			if dfs(r+d[0], c+d[1]) {
				return true
			}
		}
		path = path[:len(path)-1]
		return false
	}
	dfs(start[0], start[1])
	return path
}

func main() {
	grid := [][]bool{{true, false}, {true, true}}
	fmt.Println(MazePath(grid, [2]int{0, 0}, [2]int{1, 1}))
}