一、BFS 网格问题核心思想借助队列实现层序遍历每一层代表一步起点入队逐层向外扩散首次到达终点即为最短路径用标记位 / 原地修改网格避免重复访问搭配方向数组控制上下左右四个移动方向适用场景迷宫最短路径、网格最少步数、多源扩散、岛屿遍历防栈溢出二、基础前置工具1. 四方向数组通用// 上、下、左、右 int dir[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}};2. 队列存储结构队列中存放坐标(x, y)C 可用queuepairint, int三、模板一BFS 遍历岛屿替代 DFS原地修改网格标记已访问统计岛屿数量#include iostream #include vector #include queue using namespace std; int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; int numIslands(vectorvectorchar grid) { if(grid.empty()) return 0; int m grid.size(); int n grid[0].size(); int cnt 0; queuepairint, int q; for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1) { cnt; grid[i][j] 0; // 标记已访问 q.push({i, j}); while(!q.empty()) { auto cur q.front(); q.pop(); int x cur.first; int y cur.second; // 遍历四个方向 for(int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; if(nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } } } } return cnt; }四、模板二网格最短路径核心必考题目描述二维网格0可通行1为障碍物求从左上角(0,0)到右下角(m-1,n-1)的最短步数每移动一格步数 1。完整代码int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; int shortestPath(vectorvectorint grid) { int m grid.size(); int n grid[0].size(); // 起点/终点是障碍物直接无法通行 if(grid[0][0] 1 || grid[m-1][n-1] 1) return -1; queuepairint, int q; vectorvectorint dist(m, vectorint(n, -1)); // 距离数组 q.push({0, 0}); dist[0][0] 0; // 起点步数为0 while(!q.empty()) { auto cur q.front(); q.pop(); int x cur.first; int y cur.second; // 到达终点直接返回步数 if(x m-1 y n-1) return dist[x][y]; for(int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; // 边界合法 可通行 未访问 if(nx 0 nx m 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; // 无法到达终点 }五、多源 BFS 模板拓展题型多个起点同时向外扩散求每个位置到最近起点的距离例如「腐烂的橘子」。核心思路所有起点先全部入队再统一层序遍历int multiBfs(vectorvectorint grid) { int m grid.size(), n grid[0].size(); queuepairint,int q; int cnt 0; // 统计正常节点 // 多源所有起点先入队 for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 2) q.push({i,j}); else if(grid[i][j] 1) cnt; } } int step 0; while(!q.empty() cnt 0) { int size q.size(); // 遍历当前一整层 for(int i 0; i size; i) { auto cur q.front(); q.pop(); int x cur.first, y cur.second; for(int k 0; k 4; k) { int nx x dir[k][0]; int ny y dir[k][1]; if(nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 2; cnt--; q.push({nx, ny}); } } } step; } return cnt 0 ? step : -1; }六、DFS 与 BFS 网格题型选型对比求最短路径、最少步数、多源扩散→ 优先 BFS原理层序遍历第一次抵达就是最优解连通块统计、区域填充、遍历所有路径→ DFS / BFS 均可网格数据量极大→ 优先 BFS规避 DFS 递归栈溢出七、通用解题步骤定义四方向数组统一移动规则初始化队列起点入队并标记已访问循环取出队首坐标遍历四个方向合法新坐标入队更新步数 / 状态到达终点直接返回结果八、新手易错点忘记判断坐标越界导致数组访问异常不做访问标记节点重复入队造成死循环最短路径题不用距离数组无法记录步数多源 BFS 只入队单个起点逻辑完全错误九、今日总结BFS 依靠队列层序遍历是网格最短路径标准解法三大常用模板单岛屿遍历、单源最短路径、多源扩散方向数组 队列 访问标记 是代码标配大数据网格场景BFS 比递归版 DFS 更稳定