目录
T1. 红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
时间限制：1 s
内存限制：64 MB
- 输入
包括多个数据集合。每个数据集合的第一行是两个整数 W W W 和 H H H，分别表示 x x x 方向和 y y y 方向瓷砖的数量。 W W W 和 H H H 都不超过 20 20 20。在接下来的 H H H 行中，每行包括 W W W 个字符。每个字符表示一块瓷砖的颜色，规则如下
.：黑色的瓷砖；#：红色的瓷砖；@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
- 输出
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数（计数时包括初始位置的瓷砖）。 - 样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0 - 样例输出
45
思路分析
此题考查搜索算法求连通块大小，属于模板题。
从起点出发，执行洪水填充算法的模板，每当到达一个尚未访问的点就进行标记，并且答案累加 1 1 1。 D F S \tt DFS DFS 或 B F S \tt BFS 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 m m 行 n n n 列的格子矩阵，小 Y 从左上角 ( 1 , 1 ) (1,1) (1,1) 进入密室，密室中有三种格子：
- 墙，以数字 0 0 0 标记；
- 路，以数字 1 1 1 标记；
- 隐藏线索处，以数字 ( > 1 ) ( > 1) (>1) 标记, 代表该线索的难度。
小 Y 需要按照难度递增的顺序解开各个线索，逃脱密室。
时间限制：1 s
内存限制：64 MB
- 输入
第一行是一个整数 T T T，表示输入包含 T T T 组数据，分别是不同的游戏中小 Y 所处的密室。
对于每组数据，第一行包括两个整数： m m m（ 1 ≤ m ≤ 100 1 \le m \le 100 1≤m≤100）、 n n n（ 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100）。接下来 m m m 行，每行有