建模。把每个 1 格子看成顶点，四相邻的 1 格子之间有边——岛就是无向图的连通分量，答案就是连通分量个数。DFS 每启动一次「沉掉」一整块：扫全网格，遇到未处理的 1 就计数加一并从该格 DFS，把整块连通的 1 全部改成 0（原地标记代替 visited 数组，即「沉岛」技巧）。

代码。

#include <vector>

void sink(std::vector<std::vector<char>>& g, int r, int c) {
    if (r < 0 || r >= (int)g.size() ||
        c < 0 || c >= (int)g[0].size())
        return;                               // 越界即回
    if (g[r][c] != '1') return;               // 水 or 已访问
    g[r][c] = '0';                            // 原地标记，替代 visited
    sink(g, r + 1, c);                        // 四方向扩散
    sink(g, r - 1, c);
    sink(g, r, c + 1);
    sink(g, r, c - 1);
}

int numIslands(std::vector<std::vector<char>>& grid) {
    int rows = (int)grid.size();
    int cols = rows ? (int)grid[0].size() : 0;
    int count = 0;
    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c)
            if (grid[r][c] == '1') {          // 每发现一块新陆地
                ++count;                      // 新连通块计数
                sink(grid, r, c);             // 把整块连通陆地沉掉
            }
    return count;
}

数值演示。网格

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

扫到 (0,0) 计 1 座并沉掉左上 2×2 块；扫到 (2,2) 计 2 座；扫到 (3,3) 计 3 座并沉掉 (3,3)(3,4)。答案 3。

复杂度。时间 \(\Theta(RC)\)：每格至多被 sink 访问常数次（改 0 后不再进入）。空间 \(O(RC)\) 最坏（全陆地时递归深度）。

边界。空网格与全水（返回 0）；全陆地（返回 1，但递归最深，正是例题 2 显式栈版的动机）；「是否允许修改输入」要向面试官声明——不允许就用等大的 visited 数组，机制完全相同。

面试怎么讲。第一句话先说「岛 = 无向图连通分量，网格的隐式邻接表由四方向给出」，把图论对应讲明，再写沉岛 DFS；主动提「改输入是否允许」这一工程细节是加分项。

建模。与例题 1 同型，仅遍历实现不同——这正对应提纲「递归与迭代双实现」的要求。BFS 用队列按层沉岛；显式栈 DFS 用 vector 当栈，行为深度优先。两者的连通块答案必然一致，因为「一次启动染尽一个块」与访问顺序无关。

代码（BFS 版）。

#include <vector>
#include <queue>
#include <utility>

void sinkBFS(std::vector<std::vector<char>>& g, int r0, int c0) {
    std::queue<std::pair<int,int>> q;
    g[r0][c0] = '0';                          // 入队前标记
    q.push({r0, c0});
    const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= (int)g.size() ||
                nc < 0 || nc >= (int)g[0].size() || g[nr][nc] != '1')
                continue;
            g[nr][nc] = '0';                  // 入队时沉岛，防重复入队
            q.push({nr, nc});
        }
    }
}

代码（显式栈 DFS 版）。

#include <vector>
#include <utility>

void sinkStack(std::vector<std::vector<char>>& g, int r0, int c0) {
    std::vector<std::pair<int,int>> st{{r0, c0}};
    g[r0][c0] = '0';
    const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!st.empty()) {
        auto [r, c] = st.back(); st.pop_back();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= (int)g.size() ||
                nc < 0 || nc >= (int)g[0].size() || g[nr][nc] != '1')
                continue;
            g[nr][nc] = '0';                  // 压栈即标记
            st.push_back({nr, nc});
        }
    }
}

数值演示。在例题 1 的 4×5 网格上三种实现的计数过程完全一致（3 座），差别只在同一块内部被访问的次序：递归 DFS 与栈 DFS 是深度序（先一路向某方向走到底），BFS 是按离起点的层数序。

复杂度。两版时间均 \(\Theta(RC)\)、空间均 \(O(RC)\) 最坏，但栈深度风险消失：递归版的调用栈由系统管理且通常只有 MB 级上限，显式栈与队列都在堆上分配、可用空间大得多。10^5 级的全陆网格会让递归版直接栈溢出，这两版照常工作——这就是「同一问题双实现」在工程上的意义。

边界。与例题 1 相同；额外注意 BFS 中「入队前标记」与例题 1 递归版「进入即标记」是同一个纪律，位置不同但目的相同：每个格子恰好进一次容器。

面试怎么讲。直接以「递归会在大网格爆栈，所以我写 BFS 或显式栈」开场，把工程判断力展示出来；再说明三版答案一致性源于「连通块划分与访问顺序无关」。

建模。每条边代价都是 1 的无权图最短路——BFS 的灵魂性质直接适用：起点首次被赋值的层数就是最短步数。用 dist 矩阵替代 visited（-1 即未到达），同时充当答案容器。

代码。

#include <vector>
#include <queue>
#include <utility>

int shortestSteps(const std::vector<std::vector<int>> blocked,
                  int sr, int sc, int tr, int tc) {
    int rows = (int)blocked.size();
    int cols = rows ? (int)blocked[0].size() : 0;
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
    if (blocked[sr][sc]) return -1;           // 起点即墙
    std::queue<std::pair<int,int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});
    const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        if (r == tr && c == tc) return dist[r][c]; // 首达即最短
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (blocked[nr][nc] || dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
    return -1;                                // 队列耗尽仍未到达
}

数值演示。5×5 迷宫（# 为墙，S 起点、T 终点）：

S . . . .
. # # # .
. . . # .
# # . # .
. . . . T

BFS 的 dist 矩阵逐层填成：

0 1 2 3 4
1 # # # 5
2 3 4 # 6
# # 5 # 7
8 7 6 7 8

T 处为 8，即最少 8 步（两条最短路：左侧绕行或沿顶边绕行，长度相同）。

复杂度。时间 \(\Theta(RC)\)：每格入队一次、四邻各查一次。空间 \(\Theta(RC)\) 的 dist 与队列。

边界。起点即墙、起点等于终点（0 步）、终点被围死（返回 -1）；1×1 网格；若允许对角线移动或「穿墙」规则变化，方向数组与判重条件要同步改——规则变化类追问的本质是检查你是否理解邻接定义而非背代码。

面试怎么讲。先声明「所有边等长 ⇒ BFS 首达即最短」，再解释 dist 初始化 -1 兼任未访问标记；若面试官改成「带权网格」，主动转向 Dijkstra 的思想（006 章）并说明 BFS 不再适用。