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$ 行，每行有