网格图 · DFS / BFS 基础

1. 核心原理

网格图（grid graph）指的是这样一类问题：输入是 m × n 二维数组，每一格保存一个值（地形 / 颜色 / 高度 / 距离）；问题问"连通分量数 / 面积 / 距离 / 路径"。把每一格 (i, j) 看作图节点，相邻格之间连边，问题就退化成标准图论。

4-邻接图视角

把 m × n 网格的每一格 (i, j) 当一个节点；节点之间的边连接 (i, j) 与 (i ± 1, j)、(i, j ± 1)。这是 4-邻接图——每个内部节点度数为 4。某些题用 8-邻接（含对角线）或 6-邻接（六边形网格），但骨架一致。

常见网格题对应的图论问题：

染色法不变量

数连通分量的标准技巧是染色法：扫描整张网格，每碰到一格未访问的目标格（如 '1'）就答案 +1，并从它出发把所在连通分量全部"染掉"（标记为已访问）。核心不变量：

一旦把 (i, j) 标记为 visited，就保证这一格所在的整个连通分量都会在本次搜索中被访问到。

这意味着外层 for i, j 双重循环里碰到的每一格目标值都对应一个全新的连通分量，遇到一次 +1 即可。染色具体可以用 DFS / BFS / 并查集三种实现。

DFS vs BFS：访问顺序与取舍

DFS 用递归（或显式栈），深度优先一条路走到底，碰壁回头再换路。BFS 用队列，按层扩张，先把距源点距离 1 的格子全访问完，再访问距离 2 的。两者最终都能标记完同一个连通分量，但访问顺序不同：

原网格           DFS 访问顺序        BFS 访问顺序
1 1 1            1 → 2 → 3          1 → 2 → 5
1 1 1            8   7   4    vs    3 → 4 → 6
1 1 1            9   6   5          7 → 8 → 9
                 (深度优先)           (按距源点的层序)

DFS 路径形如一条"蛇"，BFS 路径形如扩散的"波"。两种实现的工程取舍：

选择原则：

• 小网格（m, n ≤ 100）：DFS 更简洁
• 大网格（m, n > 200，如 LC 200 的最坏）：BFS 更稳，避免 Python 递归爆栈
• 要算路径长度 / 最少步数：BFS 天然按层
• 多源扩散（下一节 多源 BFS）：BFS 才能"多个起点同时入队"

Python 默认递归深度 1000，m = n = 32 满网格全 1 时就可能爆。Java / C++ 默认栈大得多，DFS 一般够用。

染色与 visited 的工程选择

染色实现上有两种方式：

• 修改输入网格（把 '1' 改成 '0'）：省一个 O(mn) 的 visited 数组，代码短。但题目明确禁止修改输入（生产代码、并发场景）或网格类型不允许写入时，不可用。
• 独立 visited 数组：visited = [[False] * n for _ in range(m)]，访问条件改成 not visited[i][j] and grid[i][j] == '1'。更"洁净"，但内存翻倍。

无论哪种方式，染色时机必须是"入队 / 递归即染色"，不是"出队 / 处理时染色"。后者会让同一格被多次入队（最坏每个方向各一次），整体复杂度退化。

2. 通用模板

下面给 DFS 和 BFS 两种写法。Python 版同时给 DFS 与 BFS 两份；Java / C++ 给 DFS 主体（BFS 改写直接套结构）。输入都是 grid，返回岛屿数量。

# 写法一：DFS 递归
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])

        def dfs(i, j):
            # 越界 + 非目标格统一在递归入口判，简化主循环
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
                return
            grid[i][j] = '0'                       # 染色为已访问（入口处第一时间染）
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(i + di, j + dj)

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1                     # 每碰到一格未访问的 '1' = 一个新连通分量
                    dfs(i, j)
        return count


# 写法二：BFS 队列
from collections import deque

class Solution:
    def numIslandsBFS(self, grid: list[list[str]]) -> int:
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    q = deque([(i, j)])
                    grid[i][j] = '0'               # 入队即染色
                    while q:
                        x, y = q.popleft()
                        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                                grid[nx][ny] = '0' # 入队前染色，避免重复入队
                                q.append((nx, ny))
        return count

// DFS 递归
class Solution {
    int m, n;
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;                                 // 新连通分量
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        // 越界 + 非目标格统一判
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
        grid[i][j] = '0';                                    // 染色
        dfs(grid, i + 1, j); dfs(grid, i - 1, j);
        dfs(grid, i, j + 1); dfs(grid, i, j - 1);
    }
}

// DFS 递归
class Solution {
    int m, n;
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;                                 // 新连通分量
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        // 越界 + 非目标格统一判
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
        grid[i][j] = '0';                                    // 染色为已访问
        dfs(grid, i + 1, j); dfs(grid, i - 1, j);
        dfs(grid, i, j + 1); dfs(grid, i, j - 1);
    }
};

复杂度：时间 O(mn)，每一格至多被访问一次。空间 O(min(m, n)) 用 BFS 时队列宽度最坏占一对角线，或 O(mn) DFS 递归栈最坏。

模板要点：

• 越界判断与数组访问的顺序：递归入口的 if i < 0 or ... or grid[i][j] != '1' 利用短路求值——越界判断必须在数组访问之前，否则 Java / C++ 越界会抛异常。
• 方向数组 ((1, 0), (-1, 0), (0, 1), (0, -1)) 让代码紧凑。改 8-邻接只需把方向数组扩到 8 个，主逻辑不动。
• 入队 / 递归即染色：BFS 的 grid[nx][ny] = '0' 必须在 q.append((nx, ny)) 之前完成。否则同一格可能被多次入队，最坏 O(mn) 退化为 O(4mn)。
• 不要在主循环里手动判邻居是否是 '1'：交给 dfs / bfs 函数自己在入口判，代码更短、不容易漏边界。

第三种解法：并查集

把每个目标格当节点，向右 / 向下扫到目标邻居就 union，扫完一遍 parent 里有多少不同的根 = 连通分量数：

def numIslands_uf(grid: list[list[str]]) -> int:
    m, n = len(grid), len(grid[0])
    parent = list(range(m * n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # 路径折半
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb

    for i in range(m):
        for j in range(n):
            if grid[i][j] != '1':
                continue
            idx = i * n + j
            if i + 1 < m and grid[i + 1][j] == '1':
                union(idx, (i + 1) * n + j)
            if j + 1 < n and grid[i][j + 1] == '1':
                union(idx, i * n + j + 1)

    return len({find(i * n + j)
                for i in range(m) for j in range(n)
                if grid[i][j] == '1'})

复杂度 O(mn · α(mn)) ≈ O(mn)，常数比 DFS / BFS 稍大。三种解法的适用场景对比：

LC 305 Number of Islands II 是典型例子——给你一个空网格，反复"在 (r, c) 加一个 1"，每次返回当前岛屿数。DFS / BFS 每次加一格都得跑全图 O(mn)，并查集只要 O(α) 摊还。

3. 母题精讲

LeetCode 200. Number of Islands

链接：LeetCode 200

题意：给一个由 '1'（陆地）和 '0'（水）组成的二维字符网格。把上下左右相邻的陆地连成一块叫做"岛屿"。返回网格中岛屿的数量。

数据范围：

• m, n：1 到 300
• grid[i][j]：字符 '0' 或 '1'

示例：

输入：
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
解释：左上 2×2 一块、中间 (2,2) 一块、右下 (3,3)-(3,4) 一块。

暴力思路：怎么"数"才不重复算

直觉是扫一遍整个网格，遇到 '1' 就答案 +1。但这样会把同一块岛上的每一格都当成新岛，错。

正确思路：遇到 '1' 时把它所在的整块连通区域标记掉，再继续扫。问题转化成"从一个起点出发标记掉所有相邻的陆地"——这就是 §1 染色法不变量保证能 work 的场景。

直接套 §2 模板。LC 200 数据范围 m, n ≤ 300，理论最坏 9 × 10⁴ 层递归。Python 默认递归栈 1000，全 1 大网格必爆——所以 Python 解法优先 BFS，或者写 sys.setrecursionlimit(10**6)。Java / C++ 默认栈深度大，DFS 直接套模板即可。

复杂度：时间 O(mn)，空间 BFS O(min(m, n)) / DFS O(mn) 最坏递归栈。

4. 例题（三道）

按"任务复杂度递增"排：数 → 求最大 → 反向标记。每道带 follow-up 续到下一题。

4.1 LC 200 岛屿数量回头看

题目链接。题面见 §3。代码直接套 §2 模板。实战写题时几个小细节：

• 越界判断和**grid[i][j] != '1' 判断**合并在一起，先越界后访问数组。Python 短路求值，Java / C++ 也都短路（|| / or），顺序写反才会数组越界。
• 不要在主循环里手动判断"邻居是不是 1"——直接递归调用，由 dfs / bfs 函数自己在入口判。这样代码更短、不容易漏边界。
• 用 ((1, 0), (-1, 0), (0, 1), (0, -1)) 写四个方向的偏移比 4 行 dfs(i+1, j); dfs(i-1, j); ... 更紧凑。如果题目要求 8-邻接（含对角线），改成 8 个偏移即可，主体逻辑不动。

Follow-up：上面是数岛屿个数。如果题目改成"求最大岛屿的面积"——不要个数，要其中最大的那个连通分量包含多少格陆地？

4.2 LC 695 岛屿的最大面积

链接：LeetCode 695

题意：给一个 0/1 二维网格，每个 1 是陆地、0 是水。岛屿的定义同 LC 200（4-邻接）。返回所有岛屿中面积最大的那个的格子数；如果一个岛屿都没有，返回 0。

数据范围：

• m, n：1 到 50
• grid[i][j]：0 或 1（注意是整数，不是字符）

示例：

输入：grid = [
  [0,0,1,0,0,0,0,1,0,0,0,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  [0,1,0,0,1,1,0,0,1,0,1,0,0],
  [0,1,0,0,1,1,0,0,1,1,1,0,0],
  [0,0,0,0,0,0,0,0,0,0,1,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,0,0,0,0,0,0,1,1,0,0,0,0]
]
输出：6

LC 695 跟 LC 200 几乎一样，只是 dfs 不再返回 void，而是返回这次搜索访问到的格子数：

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])

        def dfs(i, j) -> int:
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1:
                return 0
            grid[i][j] = 0                          # 染色
            area = 1
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                area += dfs(i + di, j + dj)
            return area

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    ans = max(ans, dfs(i, j))
        return ans

复杂度 O(mn)。注意 dfs 的递归累加方式——area = 1 表示当前格自己贡献 1，然后四个邻居返回的子区域面积加上来。结构上和树形 DFS 求子树大小一致。

工程版可以避免修改输入：开一个 visited 数组，递归条件改成 not visited[i][j] and grid[i][j] == 1。代码长一点但更"洁净"。

Follow-up：上面两题都是从"陆地格"出发数连通分量。如果题目反过来——给一个边界连接到外界的特殊区域，要求标记所有不能从边界出去的陆地呢？

4.3 LC 130 被围绕的区域

链接：LeetCode 130

题意：给一个 m × n 的字符矩阵 board，包含 'X' 和 'O' 两种字符。把所有完全被 'X' 包围的 'O' 都翻转成 'X'。"包围"的定义是：连通的 'O' 区域里没有任何一个格子在矩阵的边界上。要求原地修改 board。

数据范围：

• m, n：1 到 200
• board[i][j]：字符 'X' 或 'O'

示例：

输入：board = [
  ["X","X","X","X"],
  ["X","O","O","X"],
  ["X","X","O","X"],
  ["X","O","X","X"]
]
输出：board = [
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","X","X","X"],
  ["X","O","X","X"]
]
解释：左下那个 'O' 在最后一行（边界）上，所以连同它本身的连通区域（只有它自己）都不翻转。中间那块 'O' 完全被 'X' 包围，翻转。

直觉是从每个内部 'O' 出发做 DFS，看能不能"逃到"边界——能逃就不翻、不能逃就翻。但这样最坏 O((mn)²) 因为每个内部 'O' 都要单独跑一次搜索。

换个方向：从边界上的 'O' 出发做 DFS / BFS，把所有能从边界到达的 'O' 都标记成一个临时字符（比如 '#'）。这些被标记的 'O' 就是"逃得出去的"。扫一遍后：

• 剩下没被标记的 'O'（即被包围的）→ 改成 'X'
• 被标记的 '#' → 改回 'O'

class Solution:
    def solve(self, board: list[list[str]]) -> None:
        if not board or not board[0]:
            return
        m, n = len(board), len(board[0])

        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
                return
            board[i][j] = '#'                       # 临时标记"逃得出去"
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(i + di, j + dj)

        # 从四条边界上的 'O' 出发
        for i in range(m):
            dfs(i, 0); dfs(i, n - 1)
        for j in range(n):
            dfs(0, j); dfs(m - 1, j)

        # 扫一遍最终改写
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'                # 被包围
                elif board[i][j] == '#':
                    board[i][j] = 'O'                # 恢复

复杂度 O(mn)。每个格子至多被访问两次（一次来自边界 DFS，一次来自最终扫描）。

这道题的核心 trick 是反向 BFS / DFS——直接从目标出发难，那就从"反目标"出发标记。这套思路在 LC 417 太平洋大西洋（多源反向 BFS）、LC 1020 飞地（边界出发的 DFS）等题里都有用。

5. 边界、易错与复杂度

越界判断与访问数组的顺序

写 dfs 时第一行通常是：

if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
    return

or 是短路求值，所以越界判断必须放在 grid[i][j] 访问之前——否则数组越界报错。Python / Java / Go 的 or、|| 都短路。

染色时机

入队 / 递归调用即染色，不是出队 / 处理时染色。否则同一格可能多次入队，复杂度退化。

DFS 版：进入 dfs(i, j) 函数体第一时间染色。 BFS 版：q.append((nx, ny)) 之前把 grid[nx][ny] = '0'。

修改输入 vs 维护 visited

修改输入网格（grid[i][j] = '0'）省一个 O(mn) 的 visited 数组，但有两个限制：

• 题目明确禁止修改原输入（生产代码、并发场景）
• 网格类型不允许写入（tuple of tuple，或冻结字符串）

不能改时开 visited = [[False] * n for _ in range(m)]，访问条件变成 not visited[i][j] and grid[i][j] == '1'，进入时 visited[i][j] = True。

Python 递归栈

Python 默认递归深度 1000。m = n = 32 满网格全 1 时递归就可能爆。两个解：

• import sys; sys.setrecursionlimit(10**6) 但内存随之上去
• 改用 BFS（用 collections.deque）

题目数据范围 m, n > 100 且语言是 Python 时，优先 BFS。Java / C++ 默认栈深度大得多，DFS 一般够用。

字符 vs 整数

注意 LC 200 网格里是字符 '1' / '0'，LC 695 / 1254 是整数 1 / 0。一字之差，判断条件不同：

if grid[i][j] == '1':    # LC 200
if grid[i][j] == 1:      # LC 695

写题前先看清楚 grid 元素是字符还是整数，判断条件相应调整。

复杂度速查

7. 小结

网格图本质就是 4-邻接的图，DFS / BFS 加上染色法是这一族题的通用骨架。掌握三件事就能套大部分网格题：

• 染色法：访问即标记，保证连通分量只被数一次。
• 反向搜索：从边界 / 海洋 / 目标反过来出发，比正向跑得快也好写。
• DFS vs BFS 取舍：小网格 DFS 简洁，大网格用 BFS 避免 Python 爆栈。

下一节 多源 BFS 把单源 BFS 推到多个起点同时扩张的场景——LC 994 腐烂的橘子、LC 542 01 矩阵、LC 1162 离海洋最远的陆地都用这个套路。多源 BFS 是网格图里求"到某一类目标的最近距离"的最干净写法。

对应灵神题单：网格图 DFS / BFS / 连通分量

进一步阅读：灵茶山艾府《网格图题单》；LeetCode DFS 标签 和 BFS 标签 高频题