程序一：网格连通块

字符 1 表示可走单元，程序按上、下、左、右四个方向搜索。完成第 1～6 题。

string a[4] = {"11000","11010","00110","00011"};
bool vis[4][5];
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
int dfs(int x,int y){
    vis[x][y]=true; int sz=1;
    for(int k=0;k<4;k++){
        int nx=x+dx[k],ny=y+dy[k];
        if(nx>=0&&nx<4&&ny>=0&&ny<5&&!vis[nx][ny]&&a[nx][ny]=='1')
            sz+=dfs(nx,ny);
    }
    return sz;
}

第 1 题

网格中共有多少个 1 连通块？

{{ input(1) }}

---

第 2 题

最大连通块大小是多少？

{{ input(2) }}

---

第 3 题

第一次从 (0,0) 调用 DFS 返回多少？

{{ input(3) }}

---

第 4 题

数组 vis 的作用是（ ）。

{{ select(4) }}

• 记录已经访问的单元，避免重复搜索
• 保存最短距离
• 对字符串排序
• 统计列数

---

第 5 题

若增加四个对角方向，两个连通块会变成几个？

{{ select(5) }}

• 1
• 2
• 3
• 4

---

第 6 题

对 $R imes C$ 网格完整扫描的时间复杂度是（ ）。

{{ select(6) }}

• $O(1)$
• $O(R+C)$
• $O(RC)$
• $O(2^{RC})$

---

程序二：迷宫 BFS

# 为障碍，S 在 (0,0)，T 在 (3,4)。完成第 7～12 题。

string a[4]={"S.#..","#.#.#",".....",".###T"};
// dist 初值为 -1，从 S 做四方向 BFS，起点距离为 0

第 7 题

S 到 T 的最短步数是多少？

{{ input(7) }}

---

第 8 题

位置 (0,1) 的距离是多少？

{{ input(8) }}

---

第 9 题

位置 (2,2) 的距离是多少？

{{ input(9) }}

---

第 10 题

位置 (3,0) 是否可达？填写 1 表示可达、0 表示不可达。

{{ input(10) }}

---

第 11 题

BFS 第一次到达 T 就得到最短路，依赖于（ ）。

{{ select(11) }}

• 每步代价相同且按距离分层扩展
• 递归深度最大
• 数组已经排序
• 使用邻接矩阵

---

第 12 题

若改用普通 DFS 并在第一次到达 T 时停止，是否保证最短？

{{ select(12) }}

• 保证
• 不保证

---

程序三：最大不相邻和

完成第 13～18 题。

int a[7]={0,4,1,1,9,1,6};
int dp[7];
dp[0]=0; dp[1]=a[1];
for(int i=2;i<=6;i++)
    dp[i]=max(dp[i-1],dp[i-2]+a[i]);

第 13 题

dp[3] 的值是多少？

{{ input(13) }}

---

第 14 题

dp[4] 的值是多少？

{{ input(14) }}

---

第 15 题

dp[6] 的值是多少？

{{ input(15) }}

---

第 16 题

转移中的 dp[i-1] 表示（ ）。

{{ select(16) }}

• 不选当前元素
• 选择当前元素
• 只选第一个元素
• 清空答案

---

第 17 题

转移中的 dp[i-2]+a[i] 表示（ ）。

{{ select(17) }}

• 选择当前元素，因此前一个不能选
• 不选当前元素
• 把所有元素相加
• 重复选择当前元素

---

第 18 题

把 max 错改为加法，最可能破坏（ ）。

{{ select(18) }}

• 两种决策取最优的含义
• 数组下标从 1 开始
• 输入格式
• 编译器版本

---