洛谷P1506-拯救oibh总部-题解

拯救oibh总部

题目背景

oibh 总部突然被水淹没了！现在需要你的救援……

题目描述

oibh 被突来的洪水淹没了，还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示，而一个四面被围墙围住的区域洪水是进不去的。

oibh 总部内部也有许多重要区域，每个重要区域在图中用一个 0 表示。

现在给出 oibh 的围墙建设图，问有多少个没被洪水淹到的重要区域。

输入格式

第一行为两个正整数 $x,y$。

接下来 $x$ 行，每行 $y$ 个整数，由 * 和 0 组成，表示 oibh 总部的建设图。

输出格式

输出没被水淹没的 oibh 总部的 0 的数量。

样例 #1

样例输入 #1

4 5
00000
00*00
0*0*0
00*00

样例输出 #1

1

样例 #2

样例输入 #2

5 5
*****
*0*0*
**0**
*0*0*
*****

样例输出 #2

5

提示

对于 $100\%$ 的数据，$1 \le x,y \le 500$。

P1506 拯救oibh总部 - 洛谷

思路

这题是不是和 洛谷P1162-填涂颜色-题解 太像了点，就是先把地图周围的0变成*，然后再遍历地图算0的数量就好了~~（又是水题，题解又能偷懒了，好耶）。甚至复制粘贴代码都能过~~

记得处理不同操作系统末尾换行的错误，不然可能本地正确，上传后错误

C++代码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    //处理不同操作系统末尾换行符不同的问题
    const auto& getcin = []() {
        int c = cin.get();
        while(c != '*' and c != '0')
            c = cin.get();
        return char(c);
    };
    int x, y, px, py, ans = 0;
    cin >> x >> y;
    vector<vector<char> > mat(x), visited(x);
    for (int i = 0; i < x; ++i) {
        mat[i].resize(y);
        visited[i].resize(y);
        for (auto &j: mat[i])
            j = getcin();
    }
    auto find = [&] {
        for (int i = 0; i < x; ++i)
            if (mat[i][0] == '0') {
                px = i, py = 0;
                return true;
            } else if (mat[i][y - 1] == '0') {
                px = i, py = y - 1;
                return true;
            }
        for (int i = 0; i < y; ++i)
            if (mat[0][i] == '0') {
                px = 0, py = i;
                return true;
            } else if (mat[x - 1][i] == '0') {
                px = x - 1, py = i;
                return true;
            }
        return false;
    };
    int dx[]{1, -1, 0, 0},
        dy[]{0, 0, 1, -1};
    while (find()) {
        queue<pair<int, int> > q;
        q.emplace(px, py);
        visited[px][py] = true;
        mat[px][py] = 0;
        while (not q.empty()) {
            int X = q.front().first, Y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; ++i) {
                px = X + dx[i], py = Y + dy[i];
                if (px >= 0 and px < x and py >= 0 and py < y
                    and not visited[px][py] and mat[px][py] == '0') {
                    mat[px][py] = '*';
                    q.emplace(px, py);
                }
            }
        }
    }
    for (auto &i: mat)
        for (auto &j: i)
            if (j == '0')
                ++ans;
    cout << ans;
    return 0;
}

AC截图