从LeetCode到ACM：迷宫最短路径的C++ BFS模板，这么写就对了

从LeetCode到ACM迷宫最短路径的C BFS模板实战精解在算法竞赛和面试刷题中迷宫类问题是最经典的场景之一。无论是LeetCode上的简单矩阵遍历还是ACM竞赛中复杂的路径搜索广度优先搜索BFS都是解决这类问题的利器。本文将为你呈现一份经过实战检验的C BFS模板它不仅适用于迷宫最短路径问题还能灵活适配各种变体题目。1. BFS核心思想与迷宫问题适配BFS之所以成为解决迷宫最短路径问题的首选算法源于其层层推进的搜索特性。想象你站在迷宫的起点每次探索所有可能的下一步位置这种策略自然保证了首次到达终点时的路径就是最短的。在实现上BFS通常需要以下几个核心组件队列Queue存储待访问的节点先进先出的特性保证了层级遍历的顺序访问标记Visited避免重复访问和形成环路方向数组定义可能的移动方向上下左右或更多对于典型的迷宫问题我们需要特别注意几个实现细节// 经典的方向数组定义 int dx[4] {-1, 0, 1, 0}; // 上、右、下、左 int dy[4] {0, 1, 0, -1};提示方向数组的定义顺序不影响算法正确性但保持一致的定义习惯可以减少编码错误2. 鲁棒性BFS模板代码解析下面是一个经过精心设计的BFS模板它考虑了各种边界情况和常见陷阱#include iostream #include queue #include cstring // 用于memset using namespace std; const int N 110; int grid[N][N]; // 迷宫矩阵 int dist[N][N]; // 记录到每个点的最短距离 int n, m; // 迷宫的行列数 int bfs() { queuepairint, int q; memset(dist, -1, sizeof dist); // 初始化为-1表示未访问 q.push({0, 0}); // 起点(0,0) dist[0][0] 0; // 起点距离为0 int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; while (!q.empty()) { auto t q.front(); q.pop(); for (int i 0; i 4; i) { int x t.first dx[i], y t.second dy[i]; // 边界检查 可通行检查 未访问检查 if (x 0 x n y 0 y m grid[x][y] 0 dist[x][y] -1) { dist[x][y] dist[t.first][t.second] 1; q.push({x, y}); // 提前终止检查 if (x n - 1 y m - 1) { return dist[x][y]; } } } } return dist[n-1][m-1]; // 保证有解的情况下不会执行到这里 } int main() { cin n m; for (int i 0; i n; i) for (int j 0; j m; j) cin grid[i][j]; cout bfs() endl; return 0; }这个模板相比原始代码有几处关键改进独立的距离数组使用dist数组专门记录距离避免混淆更安全的初始化用memset初始化距离数组为-1同时表示未访问状态更清晰的边界处理统一使用0-based索引避免1-based和0-based混用提前终止优化找到终点立即返回减少不必要的计算3. 不同OJ平台的适配技巧不同在线判题系统在题目设置和输入输出上有细微差别了解这些差异可以避免不必要的WAWrong Answer。3.1 LeetCode风格适配LeetCode通常以函数形式出题需要关注输入通常是全局变量或函数参数输出通过return返回矩阵尺寸可能不固定// LeetCode风格的BFS实现示例 class Solution { public: int shortestPathBinaryMatrix(vectorvectorint grid) { if (grid[0][0] 1) return -1; int n grid.size(); vectorvectorint dist(n, vectorint(n, -1)); queuepairint, int q; q.push({0, 0}); dist[0][0] 1; int dx[8] {-1, -1, -1, 0, 1, 1, 1, 0}; int dy[8] {-1, 0, 1, 1, 1, 0, -1, -1}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x n-1 y n-1) { return dist[x][y]; } for (int i 0; i 8; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx n ny 0 ny n grid[nx][ny] 0 dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } return -1; } };3.2 ACM/ICPC风格注意事项ACM竞赛题目通常需要处理多组测试数据文件结束判断更严格的时限和内存限制// ACM风格的多组测试数据处理 int main() { while (cin n m) { // 处理到文件结束 for (int i 0; i n; i) for (int j 0; j m; j) cin grid[i][j]; cout bfs() endl; } return 0; }4. 常见陷阱与优化技巧即使理解了BFS的基本原理实际编码中仍会遇到各种陷阱。以下是几个高频问题及解决方案4.1 步数多算一次问题初学者常犯的错误是在每次从队列取出元素时才增加步数这会导致结果多算一次。正确的做法应该是在扩展下一层节点前记录当前层的节点数。错误示例while (!q.empty()) { res; // 错误每次循环都增加步数 auto t q.front(); q.pop(); // ... }正确做法while (!q.empty()) { int levelSize q.size(); // 记录当前层的节点数 for (int i 0; i levelSize; i) { auto t q.front(); q.pop(); // 处理当前节点 } res; // 处理完一层才增加步数 }4.2 方向数组的高级用法除了基本的四方向移动BFS可以扩展到更多复杂场景八方向移动适用于更自由的移动规则代价敏感移动不同方向可能有不同代价三维空间增加z轴方向// 八方向移动示例 int dx[8] {-1, -1, -1, 0, 1, 1, 1, 0}; int dy[8] {-1, 0, 1, 1, 1, 0, -1, -1}; // 带权移动示例需要优先队列 struct State { int x, y, cost; bool operator(const State other) const { return cost other.cost; } }; priority_queueState, vectorState, greaterState pq;4.3 状态压缩与剪枝对于复杂迷宫问题可能需要记录额外状态携带钥匙使用位掩码记录获得的钥匙剩余步数记录到达当前位置时的剩余能力方向限制记录来自哪个方向// 带钥匙的状态示例 struct State { int x, y; int keys; // 使用位掩码每位代表一把钥匙 }; // 相应的访问数组 int dist[N][N][1 K]; // K是需要携带的钥匙数量5. 模板的扩展应用掌握了基础迷宫问题的BFS解法后我们可以将其应用到更广泛的场景中5.1 Flood Fill算法Flood Fill是BFS的典型应用用于连通区域填充void floodFill(vectorvectorint image, int sr, int sc, int newColor) { int oldColor image[sr][sc]; if (oldColor newColor) return; int m image.size(), n image[0].size(); queuepairint, int q; q.push({sr, sc}); image[sr][sc] newColor; int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx m ny 0 ny n image[nx][ny] oldColor) { image[nx][ny] newColor; q.push({nx, ny}); } } } }5.2 多源BFS当问题中存在多个起点时可以初始化队列时加入所有起点// 多源BFS初始化示例 queuepairint, int q; for (auto source : sources) { q.push(source); dist[source.first][source.second] 0; }5.3 双向BFS对于起点和终点都明确的问题双向BFS可以显著提高效率// 双向BFS框架示例 queueNode q1, q2; unordered_setNode visited1, visited2; q1.push(start); q2.push(end); visited1.insert(start); visited2.insert(end); while (!q1.empty() !q2.empty()) { // 交替扩展两个方向的搜索 if (expand(q1, visited1, visited2)) return true; if (expand(q2, visited2, visited1)) return true; }