当前位置：首页 > java >正文

网格图之bfs

java 2025/5/13 11:16:58

网格图的基本概念

以1210. 穿过迷宫的最少移动次数 - 力扣（LeetCode）的图为例子，这个就是网格图

一、BFS在网格图中的核心特性

1. 遍历特性

层级扩展：从起点开始逐层向外扩展，先访问所有距离为1的节点，再距离为2的节点，依此类推
队列实现：使用队列(queue)数据结构实现"先进先出"的访问顺序
最短路径保证：在无权网格中，首次访问某节点时的路径必然是最短路径

2. 网格适应特点

方向处理：通常处理4方向(上下左右)或8方向(含对角线)移动
坐标表示：用(row,col)二元组表示网格位置
边界检查：移动时需检查是否越出网格边界

二、BFS在网格图中的基本实现模版

标准实现模板

int bfs(vector<vector<char>>& grid, pair<int,int> start) {int m = grid.size(), n = grid[0].size();queue<pair<int,int>> q;vector<vector<int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 4方向移动// 初始化q.push(start);grid[start.first][start.second] = '0'; // 标记已访问int steps = 0;while(!q.empty()) {int size = q.size();for(int i = 0; i < size; i++) { // 处理当前层级所有节点auto [r,c] = q.front(); q.pop();// 处理当前节点...for(auto& dir : dirs) { // 探索相邻节点int nr = r + dir[0], nc = c + dir[1];if(nr >=0 && nr < m && nc >=0 && nc < n && grid[nr][nc] == '1') {q.push({nr,nc});grid[nr][nc] = '0'; // 标记已访问}}}steps++; // 完成一层遍历}return steps;
}

关键组件说明

队列(queue)：存储待访问节点
方向数组(dirs)：定义移动方向
层级控制：通过size = q.size()实现层级遍历
访问标记：直接修改原网格或使用独立visited数组

三、BFS在网格图中的典型应用

1. 最短路径问题

特点：

天然适合求解无权网格中的最短路径
时间复杂度O(mn)，空间复杂度O(mn)

示例场景：

迷宫最短路径
骑士最短移动步数(象棋马走日)

2. 层级扩展问题

特点：

明确知道当前处理的是第几层/第几步
可以限制扩展深度

示例场景：

病毒传播模拟
火灾蔓延预测
社交网络中的n度好友

3. 多源点问题

特点：

同时从多个起点开始BFS
适用于"最近X距离"类问题

示例场景：

每个海洋区域到最近陆地的距离(LeetCode 542)
多出发点的最短路径

五、BFS在网格图中的优化技巧

1. 双向BFS

适用场景：

起点和终点都已知的情况
大幅减少搜索空间

实现要点：

同时从起点和终点开始BFS
当两边的搜索相遇时终止

2. A*搜索

适用场景：

有权网格或需要启发式引导的情况
结合了BFS和启发式估计

3. 层级剪枝

技巧：

提前知道最大有效距离时可提前终止
某些问题不需要完整遍历整个网格

六、经典问题示例

1. 岛屿数量问题(BFS版)

cpp

复制

下载

int numIslands(vector<vector<char>>& grid) {if(grid.empty()) return 0;int m = grid.size(), n = grid[0].size();vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};int islands = 0;for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == '1') {islands++;queue<pair<int,int>> q;q.push({i,j});grid[i][j] = '0';while(!q.empty()) {auto [r,c] = q.front(); q.pop();for(auto& dir : dirs) {int nr = r + dir.first, nc = c + dir.second;if(nr >=0 && nr < m && nc >=0 && nc < n && grid[nr][nc] == '1') {q.push({nr,nc});grid[nr][nc] = '0';}}}}}}return islands;
}

2. 矩阵中的最短路径

cpp

复制

下载

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {if(grid[0][0] == 1) return -1;int n = grid.size();vector<vector<int>> dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};queue<pair<int,int>> q;q.push({0,0});grid[0][0] = 1; // 标记为已访问并用值记录步数while(!q.empty()) {auto [r,c] = q.front(); q.pop();if(r == n-1 && c == n-1) return grid[r][c];for(auto& dir : dirs) {int nr = r + dir[0], nc = c + dir[1];if(nr >=0 && nr <n && nc >=0 && nc <n && grid[nr][nc] == 0) {grid[nr][nc] = grid[r][c] + 1;q.push({nr,nc});}}}return -1;
}