数据结构与算法 / 系统课时
把网格问题转成图的连通搜索
把网格问题转成图的连通搜索
二维网格题看起来像矩阵遍历,真正决定解法的却是“哪些格子互相可达”。把合法格子视为节点、上下左右移动视为边,就能统一处理岛屿计数、区域染色和扩散问题,并用 DFS 或 BFS 控制搜索范围。
学习目标
- 能把二维网格抽象成隐式图,明确节点、邻接关系与搜索边界。
- 能用 BFS 完成连通分量计数,并正确处理访问标记。
- 能根据“找连通块”与“求最短扩散时间”的目标选择 DFS 或 BFS。
从矩阵坐标得到一张隐式图
网格题通常不需要真的构造邻接表。坐标 (r, c) 本身就是节点;若题目允许向上、下、左、右移动,那么它最多连接四个邻居。搜索时临时计算邻居即可,这种做法叫隐式建图。
例如陆地用 1、水域用 0 表示。只要两个陆地格在允许方向上相邻,就属于同一张连通子图。题目问“有多少座岛”,等价于问“图中有多少个由陆地节点组成的连通分量”。

真正容易出错的不是搜索框架,而是边界条件:越界、不可进入的格子和已经访问过的格子都必须立即跳过。只要这三个条件稳定,很多网格题都只是“起点如何选”和“搜索时记录什么”的变化。
用 BFS 统计岛屿数量
下面的完整 Java 程序扫描整个网格。每遇到一个尚未访问的陆地,就说明发现了新的连通分量;随后从该格启动 BFS,把整座岛全部标记为已访问。
import java.util.ArrayDeque;
import java.util.Queue;
public class GridIslands {
private static final int[][] DIRS = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
public static int countIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int islands = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] != '1') {
continue;
}
islands++;
bfs(grid, r, c);
}
}
return islands;
}
private static void bfs(char[][] grid, int startR, int startC) {
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{startR, startC});
// 入队时立刻标记,避免同一格被多个邻居重复加入队列。
grid[startR][startC] = '0';
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int[] d : DIRS) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr < 0 || nr >= grid.length
|| nc < 0 || nc >= grid[0].length
|| grid[nr][nc] != '1') {
continue;
}
grid[nr][nc] = '0';
queue.offer(new int[]{nr, nc});
}
}
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '0', '0', '1', '1'},
{'0', '0', '1', '0', '0'},
{'0', '0', '1', '1', '0'}
};
System.out.println(countIslands(grid));
}
}预期输出:
3这里直接把访问过的陆地改成 0,省去了额外的 visited 数组。如果题目要求保留输入,就改用同尺寸的布尔数组记录访问状态。
把同一套路迁移到区域与扩散题
“岛屿数量”是在外层扫描中统计 BFS 或 DFS 被启动了多少次;“区域染色”则从指定起点只搜索一次,并在访问节点时修改颜色;“扩散到全部目标的最短时间”通常需要 BFS 的层次信息,因为每扩展一层就对应一步或一分钟。
如果每条边的代价都相同,BFS 第一次到达某个格子时就是最短步数。若只是判断可达性或遍历完整连通块,DFS 和 BFS 都可以;递归 DFS 写法短,但深网格可能触发调用栈过深,此时显式栈或 BFS 更稳妥。
复杂度与判断方法
若网格有 R 行、C 列,每个格子最多被访问一次,每次只检查固定数量的邻居,因此时间复杂度是 O(R * C),额外空间最坏为 O(R * C)。
遇到网格题时先问三个问题:什么格子能成为节点,哪些移动算边,访问一个节点后要记录什么。能回答这三点,矩阵外观就不再重要,题目会还原成标准的图搜索问题。