第 16 章 搜索 · 知识细节练习

判断题：搜索 = 从初始状态出发，按某种规则逐步转移到新状态，直到找到目标状态或确定无解。

判断题：搜索的三要素：状态（当前局面怎么表示）、转移（一步能走到哪些状态）、目标判断（什么局面算找到答案）。

判断题：深度优先搜索（DFS）= 沿一条路径一路走到底，走不通再退回上一步换条路——不撞南墙不回头。

判断题：广度优先搜索（BFS）= 一层一层向外扩展：先看距离起点 1 步的所有状态，再看 2 步的、3 步的……

单选题：DFS 与 BFS 实现时分别用什么数据结构保存"待访问的状态"？

判断题：枚举、回溯、搜索一脉相承：枚举是最朴素的搜索；DFS/BFS 是通用的搜索框架；回溯 = DFS 加状态恢复。

判断题：DFS 最常用递归实现——递归调用栈天然扮演"待访问栈"的角色，代码简洁。

判断题：DFS 也可以用显式栈（stack）实现：把待访问节点压栈、循环弹栈访问——与递归版等价。

判断题：DFS 需要 visited 访问标记：防止重复访问节点、防止在有环的图中死循环。

判断题：DFS 先走到的分支会被完全探索完才回头——所以 DFS 的访问顺序是"先深入、后横向"。

判断题：DFS 适合：求一条可行路径、求所有解（配合回溯）、判断可达性、遍历整个图/网格。

判断题：DFS 的空间取决于深度（递归栈深），深搜一条线时占用 $O(\text{深度})$。

判断题：回溯 = DFS + 状态恢复（撤销选择）——第 14 章的回溯本质上就是 DFS。

判断题：BFS 用队列实现：起点入队，循环"出队一个、把它的未访问邻居入队"，先进先出保证按层扩展。

判断题：无权图（每步代价相同）中，BFS 第一次到达某节点的步数就是最短步数——这是 BFS 最核心的性质。

判断题：BFS 常用 dist 数组记录每个节点到起点的最短距离：dist[起点] = 0，dist[邻居] = dist[当前] + 1。

判断题：BFS 适合：无权图最短路、最少步数、按层遍历（树的层序）、连通块扩散。

判断题：BFS 的空间取决于宽度（队列最多同时保存一层/一圈的状态），可能远大于 DFS。

判断题：树的层序遍历 = BFS：一层访问完再访问下一层。

单选题：求"最少步数/最短路径"应该选？求"所有解/字典序最小解"通常选？

判断题：网格问题中状态 = 格子坐标 (r, c)；从一个格子走到相邻格子就是一次状态转移。

单选题：四方向移动的标准写法是方向数组：dx[4] = {-1, 0, 1, 0}（上、右、下、左），对应的 dy[4] 是？

判断题：八方向 = 四方向 + 四个对角方向（左上、右上、左下、右下），常用于"斜着也算相邻"的题目。

判断题：网格搜索每次向邻居移动前必须检查边界（nr >= 0 && nr < n && nc >= 0 && nc < m），否则数组越界。

判断题：网格中的障碍物（墙/不可通行格）在转移时直接跳过：if (g[nr][nc] == 1) continue;。

判断题：网格搜索同样需要访问标记（vis 二维数组或原地染色），防止同一个格子被反复访问导致死循环。

判断题：网格问题就是图问题——每个格子是一个节点，相邻可通行的格子之间有一条边。

判断题：泛洪算法（Flood Fill）= 从起点开始，把与它连通的、满足条件的区域全部扩散标记，就像墨水扩散。

判断题：泛洪的典型用途是连通块计数：遍历每个未访问的格子，每发起一次泛洪就是一个连通块。

判断题：泛洪可以用 DFS（递归）或 BFS（队列）实现，两者结果相同。

判断题：泛洪的典型应用：岛屿数量、涂色（油漆桶）、连通区域面积/周长统计。

判断题：泛洪的标记有两种：vis 数组记录"已访问"，或原地染色（把格子值改成别的数）省一个数组。

判断题：泛洪每个格子至多访问一次，复杂度 $O(\text{网格大小})$（$n \times m$ 个格子）。

判断题：迷宫求最短路径/最少步数必须用 BFS（DFS 找到的第一条路径不一定最短）。

判断题：迷宫只问"有没有一条路"（可行可达）时，DFS 和 BFS 都可以。

判断题：全排列、子集、组合这类"枚举所有方案"的问题用 DFS + 回溯（第 14 章内容）。

判断题：连通块数量（岛屿数）用泛洪：每发现一个未访问的格子就泛洪一次并计数。

判断题：求最少步数用 BFS；求字典序最小/所有解用 DFS（按字典序方向枚举）——按需求选算法。

判断题：第 10 章的图遍历（DFS/BFS + visited）就是搜索——本章把它们推广到网格、迷宫、状态空间。

判断题：搜索题的状态可以用多种方式表示——网格用坐标 (r, c)、图用节点编号、枚举用二进制 mask；选择"能装进数组、方便判重"的表示，是写搜索的第一步。

判断题：写完搜索代码必查三点：边界判断在数组访问之前、visited 在进入（DFS）或入队（BFS）时就标记、终点判断写在正确位置。

判断题：网格/图上的 DFS 递归深度过大时可能栈溢出，此时可改用 BFS 或显式栈实现——访问顺序可能不同，但能访问到的节点集合一致。

判断题：搜索顺序优化 = 先搜约束更强（可选更少）的分支——好的顺序能让搜索更快找到答案。

判断题：BFS 求最短路的适用前提是每步代价相同（无权图/等权网格）；边权不同的图不能直接用普通 BFS 求最短路。

判断题：搜索前先估算状态空间大小（如网格 $n \times m$、排列 $n!$、子集 $2^n$），判断是否会超时——超了就优化或换算法。

单选题：在有环的图上 DFS 忘记写 visited 标记，会发生？

单选题：BFS 中节点入队时不标记 visited，会发生？

单选题：网格搜索不检查边界，直接访问 g[nr][nc]，会发生？

判断题：起点与终点重合时要特判（最短步数为 0）；若忘记特判且 dist 初值设置不当，会输出错误答案。

判断题：以下结论全部正确——"DFS 一路走到底用栈、BFS 按层扩展用队列；无权图最短路用 BFS；连通块计数用泛洪；DFS/BFS 都要访问标记"。

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6];                          // 邻接矩阵（1 下标），树：1 的孩子 2、3；2 的孩子 4、5
04void dfs(int u) {
05    cout << u << " ";                  // 先访问自己（先序）
06    for (int v = 1; v <= 5; v++)
07        if (g[u][v]) dfs(v);
08}
09int main() {
10    g[1][2] = g[1][3] = 1;
11    g[2][4] = g[2][5] = 1;
12    dfs(1);
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6];                          // 树：1 的孩子 2、3；2 的孩子 4、5
04void dfs(int u) {
05    for (int v = 1; v <= 5; v++)
06        if (g[u][v]) dfs(v);
07    cout << u << " ";                  // 访问完孩子才打印（后序）
08}
09int main() {
10    g[1][2] = g[1][3] = 1;
11    g[2][4] = g[2][5] = 1;
12    dfs(1);
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04void dfs(int u) {
05    vis[u] = 1;
06    cout << u << " ";
07    for (int v = 1; v <= 5; v++)
08        if (g[u][v] && !vis[v]) dfs(v);
09}
10int main() {
11    g[1][2] = g[1][3] = 1;             // 边：1-2、1-3、2-4、2-5、3-5
12    g[2][4] = g[2][5] = g[3][5] = 1;
13    dfs(1);
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04void dfs(int u) {
05    vis[u] = 1;
06    cout << u << " ";
07    for (int v = 1; v <= 4; v++)
08        if (g[u][v] && !vis[v]) dfs(v);
09}
10int main() {
11    g[1][2] = g[2][3] = g[3][1] = 1;   // 有环：1-2-3-1
12    g[3][4] = 1;                       // 还有边 3-4
13    dfs(1);
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], dep = 0, mx = 0;
04void dfs(int u) {
05    dep++;
06    mx = max(mx, dep);                 // 记录最大递归深度
07    for (int v = 1; v <= 5; v++)
08        if (g[u][v]) dfs(v);
09    dep--;
10}
11int main() {
12    g[1][2] = g[1][3] = 1;             // 树：1 的孩子 2、3；2 的孩子 4、5
13    g[2][4] = g[2][5] = 1;
14    dfs(1);
15    cout << mx;
16    return 0;
17}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[2][2] = {{0, 0}, {0, 0}};       // 2x2 网格，0 可走
04int cnt = 0;
05void dfs(int r, int c) {               // 只能向右或向下走到 (1,1)
06    if (r == 1 && c == 1) { cnt++; return; }
07    if (r + 1 < 2) dfs(r + 1, c);      // 向下
08    if (c + 1 < 2) dfs(r, c + 1);      // 向右
09}
10int main() { dfs(0, 0); cout << cnt; return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6], cnt = 0;
04void dfs(int u) {
05    vis[u] = 1;
06    cnt++;                             // 每访问一个节点计数
07    for (int v = 1; v <= 5; v++)
08        if (g[u][v] && !vis[v]) dfs(v);
09}
10int main() {
11    g[1][2] = g[2][4] = g[2][5] = 1;   // 边：1-2、2-4、2-5（节点 3 孤立）
12    dfs(1);
13    cout << cnt;
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6];
04int main() {
05    g[1][2] = g[1][3] = 1;             // 树：1 的孩子 2、3；2 的孩子 4、5
06    g[2][4] = g[2][5] = 1;
07    queue<int> q;
08    q.push(1);
09    while (!q.empty()) {
10        int u = q.front(); q.pop();
11        cout << u << " ";
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v]) q.push(v);
14    }
15    return 0;
16}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04int main() {
05    g[1][2] = g[1][3] = 1;             // 边：1-2、1-3、2-4、2-5、3-5
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    queue<int> q;
08    q.push(1); vis[1] = 1;
09    while (!q.empty()) {
10        int u = q.front(); q.pop();
11        cout << u << " ";
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v] && !vis[v]) { vis[v] = 1; q.push(v); }
14    }
15    return 0;
16}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], dist[6];
04int main() {
05    g[1][2] = g[1][3] = 1;             // 边：1-2、1-3、2-4、2-5、3-5
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    memset(dist, -1, sizeof dist);
08    queue<int> q;
09    q.push(1); dist[1] = 0;
10    while (!q.empty()) {
11        int u = q.front(); q.pop();
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v] && dist[v] == -1) {
14                dist[v] = dist[u] + 1;
15                q.push(v);
16            }
17    }
18    cout << dist[5];
19    return 0;
20}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], dist[6];
04int main() {
05    g[1][2] = g[1][3] = 1;             // 树：1 的孩子 2、3；2 的孩子 4、5
06    g[2][4] = g[2][5] = 1;
07    memset(dist, -1, sizeof dist);
08    queue<int> q;
09    q.push(1); dist[1] = 0;
10    int mx = 0;
11    while (!q.empty()) {
12        int u = q.front(); q.pop();
13        mx = max(mx, dist[u]);
14        for (int v = 1; v <= 5; v++)
15            if (g[u][v] && dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
16    }
17    cout << mx;                        // 最大层数（根为第 0 层）
18    return 0;
19}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04int main() {
05    g[1][2] = g[1][3] = 1;
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    queue<int> q;
08    q.push(1); vis[1] = 1;
09    while (!q.empty()) {
10        int u = q.front(); q.pop();
11        cout << u << " ";              // 出队顺序 = BFS 访问顺序
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v] && !vis[v]) { vis[v] = 1; q.push(v); }
14    }
15    return 0;
16}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], dist[6];
04int main() {
05    g[1][2] = g[1][3] = 1;             // 边：1-2、1-3、2-4、2-5、3-5
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    memset(dist, -1, sizeof dist);
08    queue<int> q;
09    q.push(2); dist[2] = 0;            // 多源：2 和 3 都是起点
10    q.push(3); dist[3] = 0;
11    while (!q.empty()) {
12        int u = q.front(); q.pop();
13        for (int v = 1; v <= 5; v++)
14            if (g[u][v] && dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
15    }
16    cout << dist[5];                   // 到最近源的距离
17    return 0;
18}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6], pre[6];
04int main() {
05    g[1][2] = g[1][3] = 1;             // 边：1-2、1-3、2-4、2-5、3-5
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    queue<int> q;
08    q.push(1); vis[1] = 1;
09    while (!q.empty()) {
10        int u = q.front(); q.pop();
11        if (u == 5) break;
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v] && !vis[v]) { vis[v] = 1; pre[v] = u; q.push(v); }
14    }
15    vector<int> path;
16    for (int x = 5; x != 1; x = pre[x]) path.push_back(x);   // 从 5 回溯到 1
17    path.push_back(1);
18    for (int i = path.size() - 1; i >= 0; i--) cout << path[i] << " ";
19    return 0;
20}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[5][5] = {
04    {0,0,0,0,0},
05    {0,1,1,1,0},
06    {0,1,0,1,0},
07    {0,0,0,1,0},
08    {0,1,0,0,0}};                      // 0 可走，1 是墙
09int vis[5][5], cnt = 0;
10int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   // 上右下左
11void dfs(int r, int c) {
12    vis[r][c] = 1;
13    cnt++;
14    for (int k = 0; k < 4; k++) {
15        int nr = r + dx[k], nc = c + dy[k];
16        if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
17        if (g[nr][nc] == 1 || vis[nr][nc]) continue;
18        dfs(nr, nc);
19    }
20}
21int main() { dfs(0, 0); cout << cnt; return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[5][5] = {
04    {0,0,0,0,0},
05    {0,1,1,1,0},
06    {0,1,0,1,0},
07    {0,0,0,1,0},
08    {0,1,0,0,0}};
09int vis[5][5];
10int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
11void dfs(int r, int c) {
12    vis[r][c] = 1;
13    for (int k = 0; k < 4; k++) {
14        int nr = r + dx[k], nc = c + dy[k];
15        if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
16        if (g[nr][nc] == 1 || vis[nr][nc]) continue;
17        dfs(nr, nc);
18    }
19}
20int main() {
21    dfs(0, 0);
22    cout << (vis[4][4] ? "YES" : "NO");   // 终点 (4,4) 可达？
23    return 0;
24}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,0,0},{0,0,0}};   // 3x3 全可走
04int vis[3][3];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   // 上右下左
06void dfs(int r, int c) {
07    vis[r][c] = 1;
08    cout << r << c << " ";                 // 输出访问到的格子（行列拼写）
09    for (int k = 0; k < 4; k++) {
10        int nr = r + dx[k], nc = c + dy[k];
11        if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
12        if (vis[nr][nc]) continue;
13        dfs(nr, nc);
14    }
15}
16int main() { dfs(0, 0); return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,1,0},{0,0,0}};   // (1,1) 是墙
04int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
05void dfs(int r, int c) {
06    g[r][c] = 2;                           // 原地染色：访问过改成 2
07    for (int k = 0; k < 4; k++) {
08        int nr = r + dx[k], nc = c + dy[k];
09        if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
10        if (g[nr][nc] != 0) continue;      // 只走 0（可走且未染色）
11        dfs(nr, nc);
12    }
13}
14int main() {
15    dfs(0, 0);
16    for (int i = 0; i < 3; i++) {
17        for (int j = 0; j < 3; j++) cout << g[i][j] << " ";
18        cout << endl;
19    }
20    return 0;
21}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{1,1,0},{0,0,0},{0,0,1}};   // 1 是陆地
04int vis[3][3];
05int dx[8] = {-1,-1,-1,0,0,1,1,1}, dy[8] = {-1,0,1,-1,1,-1,0,1};  // 八方向
06void dfs(int r, int c) {
07    vis[r][c] = 1;
08    for (int k = 0; k < 8; k++) {
09        int nr = r + dx[k], nc = c + dy[k];
10        if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
11        if (g[nr][nc] == 0 || vis[nr][nc]) continue;
12        dfs(nr, nc);
13    }
14}
15int main() {
16    int cnt = 0;
17    for (int i = 0; i < 3; i++)
18        for (int j = 0; j < 3; j++)
19            if (g[i][j] == 1 && !vis[i][j]) { cnt++; dfs(i, j); }
20    cout << cnt;
21    return 0;
22}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[2][2] = {{0,1},{1,0}};              // 只有 (0,0) 和 (1,1) 可走（对角）
04int vis[2][2], cnt = 0;
05int dx[8] = {-1,-1,-1,0,0,1,1,1}, dy[8] = {-1,0,1,-1,1,-1,0,1};  // 八方向
06void dfs(int r, int c) {
07    vis[r][c] = 1;
08    cnt++;
09    for (int k = 0; k < 8; k++) {
10        int nr = r + dx[k], nc = c + dy[k];
11        if (nr < 0 || nr >= 2 || nc < 0 || nc >= 2) continue;
12        if (g[nr][nc] == 1 || vis[nr][nc]) continue;
13        dfs(nr, nc);
14    }
15}
16int main() { dfs(0, 0); cout << cnt; return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][4] = {{1,1,0,0},{1,0,0,1},{0,0,1,0}};   // 1 是陆地
04int vis[3][4];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};   // 四方向
06void dfs(int r, int c) {
07    vis[r][c] = 1;
08    for (int k = 0; k < 4; k++) {
09        int nr = r + dx[k], nc = c + dy[k];
10        if (nr < 0 || nr >= 3 || nc < 0 || nc >= 4) continue;
11        if (g[nr][nc] == 0 || vis[nr][nc]) continue;
12        dfs(nr, nc);
13    }
14}
15int main() {
16    int cnt = 0;
17    for (int i = 0; i < 3; i++)
18        for (int j = 0; j < 4; j++)
19            if (g[i][j] == 1 && !vis[i][j]) { cnt++; dfs(i, j); }
20    cout << cnt;
21    return 0;
22}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{1,1,0},{0,0,0}};   // 0 可走，1 是墙
04int dist[3][3];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06int main() {
07    memset(dist, -1, sizeof dist);
08    queue<pair<int,int>> q;
09    q.push({0, 0}); dist[0][0] = 0;
10    while (!q.empty()) {
11        auto [r, c] = q.front(); q.pop();
12        for (int k = 0; k < 4; k++) {
13            int nr = r + dx[k], nc = c + dy[k];
14            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
15            if (g[nr][nc] == 1 || dist[nr][nc] != -1) continue;
16            dist[nr][nc] = dist[r][c] + 1;
17            q.push({nr, nc});
18        }
19    }
20    cout << dist[2][2];                    // 从 (0,0) 到 (2,2) 的最短步数
21    return 0;
22}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,0,0},{0,0,0}};   // 3x3 全可走
04int dist[3][3];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06int main() {
07    memset(dist, -1, sizeof dist);
08    queue<pair<int,int>> q;
09    q.push({0, 0}); dist[0][0] = 0;        // 两个源点
10    q.push({2, 2}); dist[2][2] = 0;
11    while (!q.empty()) {
12        auto [r, c] = q.front(); q.pop();
13        for (int k = 0; k < 4; k++) {
14            int nr = r + dx[k], nc = c + dy[k];
15            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
16            if (dist[nr][nc] != -1) continue;
17            dist[nr][nc] = dist[r][c] + 1;
18            q.push({nr, nc});
19        }
20    }
21    cout << dist[1][1];                    // 到最近源点的距离
22    return 0;
23}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,0,0},{0,0,0}};
04int dist[3][3];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06int main() {
07    memset(dist, -1, sizeof dist);
08    queue<pair<int,int>> q;
09    q.push({0, 0}); dist[0][0] = 0;
10    int mx = 0;
11    while (!q.empty()) {
12        auto [r, c] = q.front(); q.pop();
13        mx = max(mx, dist[r][c]);          // 最大层数
14        for (int k = 0; k < 4; k++) {
15            int nr = r + dx[k], nc = c + dy[k];
16            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
17            if (dist[nr][nc] != -1) continue;
18            dist[nr][nc] = dist[r][c] + 1;
19            q.push({nr, nc});
20        }
21    }
22    cout << mx;
23    return 0;
24}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{1,1,0},{0,0,0}};
04int dist[3][3], cnt = 0;
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06int main() {
07    memset(dist, -1, sizeof dist);
08    queue<pair<int,int>> q;
09    q.push({0, 0}); dist[0][0] = 0;
10    while (!q.empty()) {
11        auto [r, c] = q.front(); q.pop();
12        cnt++;                             // 统计访问到的格子数
13        for (int k = 0; k < 4; k++) {
14            int nr = r + dx[k], nc = c + dy[k];
15            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
16            if (g[nr][nc] == 1 || dist[nr][nc] != -1) continue;
17            dist[nr][nc] = dist[r][c] + 1;
18            q.push({nr, nc});
19        }
20    }
21    cout << cnt;
22    return 0;
23}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{1,1,0},{0,0,0}};
04int dist[3][3];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06int main() {
07    memset(dist, -1, sizeof dist);
08    queue<pair<int,int>> q;
09    q.push({0, 0}); dist[0][0] = 0;
10    while (!q.empty()) {
11        auto [r, c] = q.front(); q.pop();
12        for (int k = 0; k < 4; k++) {
13            int nr = r + dx[k], nc = c + dy[k];
14            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
15            if (g[nr][nc] == 1 || dist[nr][nc] != -1) continue;
16            dist[nr][nc] = dist[r][c] + 1;
17            q.push({nr, nc});
18        }
19    }
20    cout << dist[2][0];                    // 从 (0,0) 到 (2,0) 的最短步数
21    return 0;
22}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,0,0},{0,0,0}};
04int dist[3][3];
05// 换一种方向顺序：左、下、右、上
06int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
07int main() {
08    memset(dist, -1, sizeof dist);
09    queue<pair<int,int>> q;
10    q.push({0, 0}); dist[0][0] = 0;
11    while (!q.empty()) {
12        auto [r, c] = q.front(); q.pop();
13        for (int k = 0; k < 4; k++) {
14            int nr = r + dx[k], nc = c + dy[k];
15            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
16            if (dist[nr][nc] != -1) continue;
17            dist[nr][nc] = dist[r][c] + 1;
18            q.push({nr, nc});
19        }
20    }
21    cout << dist[2][2];                    // 最短距离与方向顺序有关吗？
22    return 0;
23}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04int main() {
05    g[1][2] = g[1][3] = 1;
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    queue<int> q;                          // BFS 部分
08    q.push(1); vis[1] = 1;
09    while (!q.empty()) {
10        int u = q.front(); q.pop();
11        cout << u << " ";
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v] && !vis[v]) { vis[v] = 1; q.push(v); }
14    }
15    return 0;
16}

单选题：程序输出是？（同图的 DFS 顺序为 1 2 4 5 3）

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][4] = {{1,1,0,0},{1,0,0,1},{0,0,1,0}};
04int vis[3][4];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06void flood(int r, int c) {
07    vis[r][c] = 1;
08    for (int k = 0; k < 4; k++) {
09        int nr = r + dx[k], nc = c + dy[k];
10        if (nr < 0 || nr >= 3 || nc < 0 || nc >= 4) continue;
11        if (g[nr][nc] == 0 || vis[nr][nc]) continue;
12        flood(nr, nc);
13    }
14}
15int main() {
16    int cnt = 0;
17    for (int i = 0; i < 3; i++)
18        for (int j = 0; j < 4; j++)
19            if (g[i][j] == 1 && !vis[i][j]) { cnt++; flood(i, j); }
20    cout << cnt;                           // 岛屿数量
21    return 0;
22}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{1,1,0},{0,1,0},{0,1,1}};
04int vis[3][3], sz = 0;
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06void flood(int r, int c) {
07    vis[r][c] = 1;
08    sz++;                                  // 本连通块大小
09    for (int k = 0; k < 4; k++) {
10        int nr = r + dx[k], nc = c + dy[k];
11        if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
12        if (g[nr][nc] == 0 || vis[nr][nc]) continue;
13        flood(nr, nc);
14    }
15}
16int main() {
17    int mx = 0;
18    for (int i = 0; i < 3; i++)
19        for (int j = 0; j < 3; j++)
20            if (g[i][j] == 1 && !vis[i][j]) { sz = 0; flood(i, j); mx = max(mx, sz); }
21    cout << mx;                            // 最大连通块大小
22    return 0;
23}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{1,1,0},{1,0,0},{0,0,0}};   // 1 是陆地
04int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
05void flood(int r, int c) {
06    g[r][c] = 2;                           // 原地染色
07    for (int k = 0; k < 4; k++) {
08        int nr = r + dx[k], nc = c + dy[k];
09        if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
10        if (g[nr][nc] != 1) continue;      // 只染陆地
11        flood(nr, nc);
12    }
13}
14int main() {
15    flood(0, 0);
16    for (int i = 0; i < 3; i++) {
17        for (int j = 0; j < 3; j++) cout << g[i][j] << " ";
18        cout << endl;
19    }
20    return 0;
21}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[2][2] = {{1,1},{1,0}};               // 3 块陆地
04int vis[2][2], ans = 0;
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06void flood(int r, int c) {
07    vis[r][c] = 1;
08    for (int k = 0; k < 4; k++) {
09        int nr = r + dx[k], nc = c + dy[k];
10        if (nr < 0 || nr >= 2 || nc < 0 || nc >= 2) { ans++; continue; }  // 边界算周长
11        if (g[nr][nc] == 0) ans++;         // 靠海一边算周长
12        else if (!vis[nr][nc]) flood(nr, nc);
13    }
14}
15int main() { flood(0, 0); cout << ans; return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[4][4] = {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};   // 4x4 全陆地
04int vis[4][4], cnt = 0;
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06void flood(int r, int c) {
07    vis[r][c] = 1;
08    if (r == 0 || c == 0 || r == 3 || c == 3) cnt++;   // 统计边界格
09    for (int k = 0; k < 4; k++) {
10        int nr = r + dx[k], nc = c + dy[k];
11        if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue;
12        if (vis[nr][nc]) continue;
13        flood(nr, nc);
14    }
15}
16int main() { flood(0, 0); cout << cnt; return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[2][3] = {{0,0,0},{0,0,0}};          // 2 行 3 列
04int cnt = 0;
05void dfs(int r, int c) {                   // 只能向右或向下，从 (0,0) 到 (1,2)
06    if (r == 1 && c == 2) { cnt++; return; }
07    if (r + 1 < 2) dfs(r + 1, c);
08    if (c + 1 < 3) dfs(r, c + 1);
09}
10int main() { dfs(0, 0); cout << cnt; return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,0,0},{0,0,0}};
04int dist[3][3], level[10] = {0};
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06int main() {
07    memset(dist, -1, sizeof dist);
08    queue<pair<int,int>> q;
09    q.push({0, 0}); dist[0][0] = 0;
10    while (!q.empty()) {
11        auto [r, c] = q.front(); q.pop();
12        level[dist[r][c]]++;               // 统计每层的格子数
13        for (int k = 0; k < 4; k++) {
14            int nr = r + dx[k], nc = c + dy[k];
15            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
16            if (dist[nr][nc] != -1) continue;
17            dist[nr][nc] = dist[r][c] + 1;
18            q.push({nr, nc});
19        }
20    }
21    for (int i = 0; i <= 4; i++) cout << level[i] << " ";
22    return 0;
23}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,1,0},{0,0,0}};   // (1,1) 是墙
04int dist[3][3];
05pair<int,int> pre[3][3];
06int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
07int main() {
08    memset(dist, -1, sizeof dist);
09    queue<pair<int,int>> q;
10    q.push({0, 0}); dist[0][0] = 0;
11    while (!q.empty()) {
12        auto [r, c] = q.front(); q.pop();
13        for (int k = 0; k < 4; k++) {
14            int nr = r + dx[k], nc = c + dy[k];
15            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
16            if (g[nr][nc] == 1 || dist[nr][nc] != -1) continue;
17            dist[nr][nc] = dist[r][c] + 1;
18            pre[nr][nc] = {r, c};
19            q.push({nr, nc});
20        }
21    }
22    vector<pair<int,int>> path;
23    for (auto p = make_pair(2, 2); p != make_pair(0, 0); p = pre[p.first][p.second])
24        path.push_back(p);                 // 从终点回溯
25    path.push_back({0, 0});
26    for (int i = path.size() - 1; i >= 0; i--)
27        cout << path[i].first << path[i].second << " ";
28    return 0;
29}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[3][3] = {{0,0,0},{0,0,0},{0,0,0}};   // 3x3 全可走
04int dist[3][3];
05int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
06int main() {
07    memset(dist, -1, sizeof dist);
08    queue<pair<int,int>> q;
09    q.push({0, 2}); dist[0][2] = 0;        // 两个出口先入队（多源 BFS）
10    q.push({2, 0}); dist[2][0] = 0;
11    while (!q.empty()) {
12        auto [r, c] = q.front(); q.pop();
13        for (int k = 0; k < 4; k++) {
14            int nr = r + dx[k], nc = c + dy[k];
15            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
16            if (dist[nr][nc] != -1) continue;
17            dist[nr][nc] = dist[r][c] + 1;
18            q.push({nr, nc});
19        }
20    }
21    cout << dist[1][1];                    // 从 (1,1) 到最近出口的步数
22    return 0;
23}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 3;                             // 3 个物品，每个选/不选
05    int cnt = 0;
06    for (int mask = 0; mask < (1 << n); mask++) cnt++;   // mask 的每一位代表一个物品
07    cout << cnt;                           // 子集总数
08    return 0;
09}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int cnt = 0;
04void dfs(int r, int c) {                   // 3x3 网格，只能向右或向下（限定方向）
05    if (r == 2 && c == 2) { cnt++; return; }
06    if (r + 1 < 3) dfs(r + 1, c);
07    if (c + 1 < 3) dfs(r, c + 1);
08}
09int main() { dfs(0, 0); cout << cnt; return 0; }

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04void dfs(int u) {
05    vis[u] = 1;
06    cout << u << " ";
07    for (int v = 1; v <= 5; v++)
08        if (g[u][v] && !vis[v]) ______;    // 递归访问邻居
09}
10int main() {
11    g[1][2] = g[1][3] = 1;
12    g[2][4] = g[2][5] = g[3][5] = 1;
13    dfs(1);
14    return 0;
15}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04void dfs(int u) {
05    ______;                     // 标记当前节点已访问
06    cout << u << " ";
07    for (int v = 1; v <= 5; v++)
08        if (g[u][v] && !vis[v]) dfs(v);
09}
10int main() {
11    g[1][2] = g[1][3] = 1;
12    g[2][4] = g[2][5] = g[3][5] = 1;
13    dfs(1);
14    return 0;
15}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04int main() {
05    g[1][2] = g[1][3] = 1;
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    queue<int> q;
08    q.push(1); vis[1] = 1;
09    while (______) {
10        int u = q.front(); q.pop();
11        cout << u << " ";
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v] && !vis[v]) { vis[v] = 1; q.push(v); }
14    }
15    return 0;
16}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int g[6][6], vis[6];
04int main() {
05    g[1][2] = g[1][3] = 1;
06    g[2][4] = g[2][5] = g[3][5] = 1;
07    queue<int> q;
08    q.push(1); vis[1] = 1;
09    while (!q.empty()) {
10        int u = q.front(); q.pop();
11        cout << u << " ";
12        for (int v = 1; v <= 5; v++)
13            if (g[u][v] && !vis[v]) {
14                vis[v] = 1;    // 入队时立即标记
15                ______;
16            }
17    }
18    return 0;
19}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03int dx[4] = {-1, 0, 1, 0};     // 上、右、下、左
04int dy[4] = ______;
05int main() {
06    // 用 dx/dy 实现网格四方向移动
07    return 0;
08}