数据结构与算法 / 系统课时

把网格问题转成图的连通搜索

把网格问题转成图的连通搜索

二维网格题看起来像矩阵遍历,真正决定解法的却是“哪些格子互相可达”。把合法格子视为节点、上下左右移动视为边,就能统一处理岛屿计数、区域染色和扩散问题,并用 DFS 或 BFS 控制搜索范围。

学习目标

  • 能把二维网格抽象成隐式图,明确节点、邻接关系与搜索边界。
  • 能用 BFS 完成连通分量计数,并正确处理访问标记。
  • 能根据“找连通块”与“求最短扩散时间”的目标选择 DFS 或 BFS。

从矩阵坐标得到一张隐式图

网格题通常不需要真的构造邻接表。坐标 (r, c) 本身就是节点;若题目允许向上、下、左、右移动,那么它最多连接四个邻居。搜索时临时计算邻居即可,这种做法叫隐式建图。

例如陆地用 1、水域用 0 表示。只要两个陆地格在允许方向上相邻,就属于同一张连通子图。题目问“有多少座岛”,等价于问“图中有多少个由陆地节点组成的连通分量”。

二维网格转成隐式图并进行 BFS

真正容易出错的不是搜索框架,而是边界条件:越界、不可进入的格子和已经访问过的格子都必须立即跳过。只要这三个条件稳定,很多网格题都只是“起点如何选”和“搜索时记录什么”的变化。

用 BFS 统计岛屿数量

下面的完整 Java 程序扫描整个网格。每遇到一个尚未访问的陆地,就说明发现了新的连通分量;随后从该格启动 BFS,把整座岛全部标记为已访问。

java
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));
    }
}

预期输出:

text
3

这里直接把访问过的陆地改成 0,省去了额外的 visited 数组。如果题目要求保留输入,就改用同尺寸的布尔数组记录访问状态。

把同一套路迁移到区域与扩散题

“岛屿数量”是在外层扫描中统计 BFS 或 DFS 被启动了多少次;“区域染色”则从指定起点只搜索一次,并在访问节点时修改颜色;“扩散到全部目标的最短时间”通常需要 BFS 的层次信息,因为每扩展一层就对应一步或一分钟。

如果每条边的代价都相同,BFS 第一次到达某个格子时就是最短步数。若只是判断可达性或遍历完整连通块,DFS 和 BFS 都可以;递归 DFS 写法短,但深网格可能触发调用栈过深,此时显式栈或 BFS 更稳妥。

复杂度与判断方法

若网格有 R 行、C 列,每个格子最多被访问一次,每次只检查固定数量的邻居,因此时间复杂度是 O(R * C),额外空间最坏为 O(R * C)。

遇到网格题时先问三个问题:什么格子能成为节点,哪些移动算边,访问一个节点后要记录什么。能回答这三点,矩阵外观就不再重要,题目会还原成标准的图搜索问题。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

把网格问题转成图的连通搜索

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通