信息奥赛题解

发布日期: 2023-05-20

文章字数: 1.7k

阅读时长: 7 分

阅读次数:

信息奥赛题解｜流感传染

🚀 题目浏览

【题目描述】

有一批易感人群住在网格状的宿舍区内，宿舍区为 $n*n$ 的矩阵，每个格点为一个房间，房间里可能住人，也可能空着。

在第一天，有些房间里的人得了流感，以后每天，得流感的人会使其邻居传染上流感（已经得病的不变），空房间不会传染。

请输出第 $m$ 天得流感的人数。

【输入】

第一行一个数字 $n$，$n$ 不超过 $100$，表示有 $n*n$ 的宿舍房间。

接下来的 $n$ 行，每行 $n$ 个字符，’.’ 表示第一天该房间住着健康的人，’#’ 表示该房间空着，’@’ 表示第一天该房间住着得流感的人。

接下来的一行是一个整数 $m$，$m$ 不超过 $100$。

【输出】

输出第 $m$ 天，得流感的人数。

【输入样例】

5
....#
.#.@.
.#@..
#....
.....
4

【输出样例】

【原题链接】

http://ybt.ssoier.cn:8088/problem_show.php?pid=1191

☘️ 题解分析

在摊主看来，本题对于 算法初学者 主要有以下几个难点：

如何读入字符矩阵？
如何模拟感染过程？

对于第一个难点，摊主采用的方式是「定义一个 二维的字符数组、使用 cin 读入数据」（需要开启 cin 读入优化，减少读入数据的时间）。

const int N = 105;
char s[N][N];  // 定义一个二维的字符数组

int main(){
    //cin 读入优化
    ios::sync_with_stdio(false);
    cin.tie(0);
  
    //读入矩阵
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> s[i][j];
        }
    }
    return 0;
}

🍉 PS：使用 scanf 读入时，需要考虑 换行符的读入，而 cin 则不用，这是 scanf 的缺点；但 scanf 的读入速度比没有开 cin 读入优化的 cin 快很多，这是 scanf 的优点。

cin 在开了 cin 读入优化后，速度基本上能达到 scanf 的水平，此题完全够用了。

对于第二个难点，摊主采用了 遍历模拟 的方法，每天都遍历一次二维矩阵，模拟感染过程。

模拟过程也非常简单，只需在遍历时，遇到 ‘@’ 的房间，就把四周非空的房间置为 ‘@’

❗️❗️❗️但是这种方式非常容易出现 一个误区，就是「每次矩阵还没有遍历完，就急着把 当前房间感染的新房间置为 ‘@’ 」

这样会出现下面这种情况：

第一天，初始情况

@..
#..

第二天，遍历到第 1 个房间时

@@.
#..

第二天，遍历到第 2 个房间时，由于当前房间被置为了 ‘@’，所以其周围的房间也被置为 ‘@’

@@@
#@.

第二天，遍历到第 3 个房间时，由于当前房间被置为了 ‘@’，所以其周围的房间也被置为 ‘@’

@@@
#@@

… 省略剩下的遍历过程
第二天的最终结果

@@@
#@@

这样的得到的结果显然是不对的 ❌

因为实际上第 2 天，仅有 2 号房间被感染，3 号房间需要等到第 3 天才会被感染。✅

第二天实际结果

@@.
#..

所以，我们需要借助一个标记数组 b，存储当天被感染的房间，而不是在遍历时直接修改原矩阵的值。

等当天的 遍历结束后，再根据标记数组 b 来修改原矩阵的值，这样就不会出现上面这种情况了。

从代码的角度，是这样的区别：

//模拟感染过程，并标记
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (s[i][j] == '@') {
            // 错误的直接修改法
            //if (s[i - 1][j] != '#') s[i - 1][j] = '@';
            //if (s[i + 1][j] != '#') s[i + 1][j] = '@';
            //if (s[i][j - 1] != '#') s[i][j - 1] = '@';
            //if (s[i][j + 1] != '#') s[i][j + 1] = '@';
          
            // 正确的标记法
            if (s[i - 1][j] != '#') b[i - 1][j] = 1;
            if (s[i + 1][j] != '#') b[i + 1][j] = 1;
            if (s[i][j - 1] != '#') b[i][j - 1] = 1;
            if (s[i][j + 1] != '#') b[i][j + 1] = 1;
        }
    }
}

//将带有标记的房间感染
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (b[i][j] == 1) {
            s[i][j] = '@';
        }
    }
}

PS 🍉：本题也可以使用 广度优先搜索 BFS 的方法求解，具体代码见下文。

🧑🏻‍💻 C++ 代码

模拟

#include<bits/stdc++.h>

using namespace std;
const int N = 105;

char s[N][N];  // 存储房间状态
int b[N][N];  //用于感染的标记数组
int n, m, cnt;

// 每天更新矩阵
void update();

// 统计并输出感染人数
void print();

int main() {
    ios::sync_with_stdio(false);  // cin读入优化
    cin.tie(0);

    //读入矩阵
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> s[i][j];
        }
    }

    // 统计第m天，需要更新m-1次
    cin >> m;
    while (--m) {
        //更新矩阵
        update();
    }

    // 统计感染总人数
    print();

    return 0;
}


void update() {
    //初始化感染标记数组b
    memset(b, 0, sizeof(b));

    //模拟感染过程，并标记
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // 向四个方向进行感染，标记位置
            // 注意不能马上把相应房间改为 @，否则会出现一条线上的房间一天就感染完等情况
            if (s[i][j] == '@') {
                if (s[i - 1][j] != '#') b[i - 1][j] = 1;
                if (s[i + 1][j] != '#') b[i + 1][j] = 1;
                if (s[i][j - 1] != '#') b[i][j - 1] = 1;
                if (s[i][j + 1] != '#') b[i][j + 1] = 1;
            }
        }
    }

    //将带有标记的房间感染
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (b[i][j] == 1) {
                s[i][j] = '@';
            }
        }
    }
}

void print() {
    cnt = 0;
    //统计感染人数
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s[i][j] == '@')
                cnt++;
        }
    }
    cout << cnt << endl;
}

BFS

#include<bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const int N = 1e2 + 10;
char a[N][N];
int n, m, ans;
int dx[4] = {-1, +1, 0, 0}; // 方向数组
int dy[4] = {0, 0, +1, -1};
queue<PII> q, tmp;  // BFS队列

// bfs返回新感染的人数
int bfs() {
    // q存储当天初始的感染人的坐标
    // tmp存储当天新感染的人的坐标
    // pop()当天q中的坐标，并将四周符合条件的坐标push()到tmp中
    while (!q.empty()) {
        // q的队首元素
        PII h = q.front();
        q.pop();
        int x = h.first, y = h.second;
        
        // 感染四周
        for (int i = 0; i < 4; i++) {
            int x1 = x + dx[i], y1 = y + dy[i];
            if (a[x1][y1] == '.') {
                a[x1][y1] = '@';
                tmp.push({x1, y1});
            }
        }
    }
    // 统计当天感染人数（即tmp中的元素数量），并将tmp中的元素全部push()到q中，便于下一天计算
    int cnt = 0;
    while (!tmp.empty()) {
        PII head = tmp.front();
        cnt++;
        q.push(head);
        tmp.pop();
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            // 将初始感染人数入队
            if (a[i][j] == '@') q.push({i, j}), ans++;
        }
    }

    cin >> m;  // m天（m==1为初始状态）
    // bfs返回新感染的人数
    for (int i = 1; i < m; i++) ans += bfs();
    cout << ans << endl;
    return 0;
}