当前位置：首页 > article >正文

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

article 2025/1/12 21:57:31

T1. 红与黑

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

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

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

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

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

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

样例输入

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

样例输出
```
45
```

思路分析

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

从起点出发，执行洪水填充算法的模板，每当到达一个尚未访问的点就进行标记，并且答案累加 $1$ 。 $\tt DFS$ 或 $\tt 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;
}