2021 年 3 月青少年软编等考 C 语言五级真题解析

T1. 红与黑

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

时间限制：1 s
内存限制：64 MB

• 输入
  包括多个数据集合。每个数据集合的第一行是两个整数 $W$ 和 $H$，分别表示 $x$ 方向和 $y$ 方向瓷砖的数量。$W$ 和 $H$ 都不超过 $20$。在接下来的 $H$ 行中，每行包括 $W$ 个字符。每个字符表示一块瓷砖的颜色，规则如下

1. .：黑色的瓷砖；
2. #：红色的瓷砖；
3. @’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

• 输出
  对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数（计数时包括初始位置的瓷砖）。
• 样例输入

  6 9 
  ....#. 
  .....# 
  ...... 
  ...... 
  ...... 
  ...... 
  ...... 
  #@...# 
  .#..#. 
  0 0
  

• 样例输出

  45
  

思路分析

此题考查搜索算法求连通块大小，属于模板题。

从起点出发，执行洪水填充算法的模板，每当到达一个尚未访问的点就进行标记，并且答案累加 $1$。$\mathtt{DFS}$ 或 $\mathtt{BFS}$ 均可实现。

/** Name: T1.cpp* Problem: 红与黑* Author: Teacher Gao.* Date&Time: 2025/01/03 18:32*/#include <iostream>
#include <cstring>using namespace std;int n, m, tot;
char a[25][25];
bool f[25][25];int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};void dfs(int x, int y) {for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (f[nx][ny] || a[nx][ny] == '#') continue;f[nx][ny] = 1;tot++;dfs(nx, ny);}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int sx, sy;while (cin >> m >> n && n && m) {memset(a, 0, sizeof(a));memset(f, 0, sizeof(f));for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];if (a[i][j] == '@') {sx = i, sy = j;tot = f[i][j] = 1;}}}dfs(sx, sy);cout << tot << "\n";}return 0;
}

T2. 密室逃脱

小 Y 喜欢玩密室逃脱，每次游戏开始时，小 Y 会进入一个密室，她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小 Y 非常聪明，解开线索对她来说并不难，但是她有一点懒，她希望在通关过程中移动次数最少。请你帮小 Y 计算她至少要移动多少次才能成功通关。

密室是 $m$ 行 $n$ 列的格子矩阵，小 Y 从左上角 $(1,1)$ 进入密室，密室中有三种格子：

• 墙，以数字 $0$ 标记；
• 路，以数字 $1$ 标记；
• 隐藏线索处，以数字 $(>1)$ 标记, 代表该线索的难度。

小 Y 需要按照难度递增的顺序解开各个线索，逃脱密室。

时间限制：1 s
内存限制：64 MB

• 输入
  第一行是一个整数 $T$，表示输入包含 $T$ 组数据，分别是不同的游戏中小 Y 所处的密室。
  对于每组数据，第一行包括两个整数：$m$（$1\le m\le 100$）、$n$（$1\le n\le 100$）。接下来 $m$ 行，每行有