Oiclass P1202 题解

这道题一看就是连通块

因为求连通块 DFS 最简单，所以我用 BFS

简单思路：

首先把外围的 0 给清除掉，然后统计数组里面还有多少个 0。

那么难点来了，究竟怎样能一次把外围所有的 0 给清除呢？记不记得我们在输入的时候一般都会从 [1][1] 开始输入，那么是不是从 [1][1] 到 [n][n] 都有值？没错，有脑子都知道有值，那么这个矩阵的四周是不是空出了一圈是没有值的，就像这样：

\0 \0 \0
\0 值 \0
\0 \0 \0

那么我们如果将外围的所有部分当做一个连通块来求的话，我们就可以把被 * 包围的 0 以外的所有部分找到，那么如果我们把所有部分都标记成 * 然后再遍历一次数组，把所有的 0 的个数统计起来，输出，那么是不是就可以 AC 了，不好意思，你太天真了，如果我们将这样的思路直接模拟出代码，那么 bfs 函数应该是这样的：

struct pos{
    int x, y;
};

queue<pos> q;
void bfs(int x, int y){
    q.push((pos){x, y});
    while (!q.empty()){
        pos k = q.front();
        q.pop();
        for (int i=0; i <= 3; i++){
            if (c[k.x + xx[i]][k.y + yy[i]] != '*'){
                q.push((pos){k.x + xx[i], k.y + yy[i]});
                c[k.x + xx[i]][k.y + yy[i]] = '*';
            }
        }
    }
}

如果就这样自信运行的话那么你就会发现他报错 EXC_BAD_ACCESS (code=2, address=0x10b999e28) （我用 LLDB 看的）为什么呢？

如果我们用 LLDB 检测两个下标的数值，就会发现我们的下标变成了负数（我也是服了），要怎么避免呢？我们可以引入一个 bool check(int x, int y) 函数，用来检查下标的有效性。函数如下：

bool check(int x, int y){
    if (x < 0 || y < 0 || x > a + 1 || y > b + 1 || c[x][y] == '*'){
        return false;
    }
    return true;
}

你可能会好奇为什么要检查是否过大呢？实际上这样可以使得速度加快，减少 BFS 的块。

好的，那么坑都解决了，对吗？可能对吧，至少我遇到过的就这些，那么代码写出来是什么样子的呢？

就长这样：(都看到这里了，点个赞吧，球球了)

#include <iostream>
#include <queue>

using namespace std;

struct pos { // 存储位置的结构体
    int x, y;
};

int a, b, cnt, xx[4] = {-1, 1, 0, 0}, yy[4] = {0, 0, -1, 1}; // 偏移量，一些基本的变量，a: x, b: y
char c[520][520]; // 数字看起来不错吧

bool check(int x, int y) {
    if (x < 0 || y < 0 || x > a + 1 || y > b + 1 || c[x][y] == '*') { // 检测越界和围墙
        return false;
    }
    return true;
}

queue<pos> q;

void clear(int x, int y) {
    // 这个函数用来清空外围被水淹的服务器，函数本质上就是广搜找连通块，然后标记
    q.push((pos) {x, y});
    while (!q.empty()) {
        pos k = q.front(); // 获取对首
        q.pop();
        for (int i = 0; i <= 3; i++) {
            if (check(k.x + xx[i], k.y + yy[i])) { // 确认不是围墙或者数组越界
                q.push((pos) {k.x + xx[i], k.y + yy[i]}); // 将其加入队列
                c[k.x + xx[i]][k.y + yy[i]] = '*'; // 标记为围墙，即清空
            }
        }
    }
}

int main() {
    // 简单输入不用讲吧
    cin >> a >> b;
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            cin >> c[i][j];
        }
    }
    // 用 [0][0] 来检测外部的连通块用来清除被洪水淹没的服务器
    clear(0, 0);
    // 检测清除完以后还有多少台幸存的服务器
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            if (c[i][j] == '0') {
                cnt += 1;
            }
        }
    }
    // 无脑输出
    cout << cnt;
}

截屏2022-12-05 09.10.01