迷宫寻路
进阶迷宫寻路把"搜索路径"这个概念直观地落在二维空间里。
// 算法讲解
迷宫寻路
在随机生成的迷宫中用回溯法寻找从左上到右下的路径。
待机
速度 中
待机 ⌨1bool dfs(int x, int y) {
2 if (x == targetX && y == targetY) return true;
3 visited[x][y] = true;
4 for (int dir = 0; dir < 4; dir++) {
5 int nx = x + dx[dir];
6 int ny = y + dy[dir];
7 if (!inside(nx, ny) || blocked(nx, ny) || visited[nx][ny]) continue;
8 if (dfs(nx, ny)) return true;
9 }
10 visited[x][y] = false;
11 return false;
12}
复杂度分析
时间 最坏 O(R*C)
空间 O(R*C)
最优 命中即停
最坏 遍历整图
算法讲解
从起点出发，递归尝试上下左右四个方向，只走边界内且未访问过的格子。
如果某条路最终到不了终点，就撤销标记并回退，这正是回溯名字的来源。
它能很好地帮助理解 DFS、visited 数组和路径恢复三者之间的关系。
当地图更大或边权不同时，再继续扩展到 BFS、最短路或 A* 会非常自然。