迷宫路径搜索问题：BFS与DFS算法详解

问题描述这是一个经典的迷宫路径搜索问题。给定一个 n × n 的字符矩阵迷宫其中 . 表示通路# 表示墙壁。同时给出起点坐标 (ha, la) 和终点坐标 (hb, lb)。规则是只能向上、下、左、右四个方向移动不能走出边界也不能走到 # 上。目标是判断是否能从起点走到终点。特殊情况如果起点或终点本身就是墙壁 #则直接输出 NO。算法选择我们可以使用广度优先搜索 (BFS)或深度优先搜索 (DFS)来解决。BFS 是解决此类最短路径或连通性问题的标准方法而 DFS 代码通常更简洁。C 代码实现BFS版本这里使用 BFS广度优先搜索实现#include iostream #include vector #include queue #include string using namespace std; // 定义方向数组上、下、左、右 int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; // 定义坐标结构体 struct Point { int x, y; }; void solve() { int n; cin n; // 存储迷宫地图 vectorstring maze(n); for (int i 0; i n; i) { cin maze[i]; } int ha, la, hb, lb; cin ha la hb lb; // 特判如果起点或终点是墙壁直接无法到达 if (maze[ha][la] # || maze[hb][lb] #) { cout NO endl; return; } // 记录是否访问过该点防止重复走 vectorvectorbool visited(n, vectorbool(n, false)); queuePoint q; // 将起点加入队列并标记为已访问 q.push({ha, la}); visited[ha][la] true; bool found false; while (!q.empty()) { Point curr q.front(); q.pop(); // 如果当前点是终点说明找到了路径 if (curr.x hb curr.y lb) { found true; break; } // 尝试向四个方向移动 for (int i 0; i 4; i) { int nx curr.x dx[i]; int ny curr.y dy[i]; // 检查边界条件 // 1. 不越界 (0 nx n 且 0 ny n) // 2. 不是墙壁 (maze[nx][ny] ! #) // 3. 没有被访问过 (!visited[nx][ny]) if (nx 0 nx n ny 0 ny n maze[nx][ny] ! # !visited[nx][ny]) { visited[nx][ny] true; // 标记为已访问 q.push({nx, ny}); // 加入队列 } } } if (found) { cout YES endl; } else { cout NO endl; } } int main() { // 优化输入输出效率 ios_base::sync_with_stdio(false); cin.tie(NULL); int k; if (cin k) { while (k--) { solve(); } } return 0; }代码关键点解析数据结构vectorstring maze用来存储迷宫地图string 可以直接通过下标访问字符非常方便。queuePointBFS 的核心队列用来存放待探索的坐标。vectorvectorbool visited这是一个二维布尔数组用来记录哪些格子已经走过了。非常重要如果不记录程序会在两个格子之间无限循环导致超时或崩溃。边界检查在尝试移动到新坐标 (nx, ny) 时必须首先检查nx 0 nx n等条件防止数组越界访问。多组数据题目第一行输入 k表示有 k 组数据所以主函数里用了一个while(k--)循环来调用处理逻辑。DFS版本实现这题用 BFS 是最稳妥的其实用 DFS递归写起来代码更短#include iostream #include vector #include string using namespace std; int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; bool dfs(vectorstring maze, vectorvectorbool visited, int x, int y, int hb, int lb) { if (x hb y lb) return true; visited[x][y] true; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx maze.size() ny 0 ny maze.size() maze[nx][ny] ! # !visited[nx][ny]) { if (dfs(maze, visited, nx, ny, hb, lb)) { return true; } } } return false; } void solve() { int n; cin n; vectorstring maze(n); for (int i 0; i n; i) { cin maze[i]; } int ha, la, hb, lb; cin ha la hb lb; if (maze[ha][la] # || maze[hb][lb] #) { cout NO endl; return; } vectorvectorbool visited(n, vectorbool(n, false)); if (dfs(maze, visited, ha, la, hb, lb)) { cout YES endl; } else { cout NO endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int k; if (cin k) { while (k--) { solve(); } } return 0; }算法对比特性BFSDFS代码复杂度中等需要队列简单递归实现空间复杂度O(n²)队列可能存储大量节点O(n²)递归栈深度适用场景求最短路径判断连通性本题推荐更稳妥不易栈溢出代码简洁总结迷宫路径搜索是图论中的基础问题BFS 和 DFS 都是有效的解决方法。BFS 更适合需要最短路径的场景而 DFS 代码更简洁。在实际解题时可以根据题目要求和数据规模选择合适的算法。