P8662 题解

amaimaic · 2023-04-01 23:00:20 · 题解

一道深度优先搜索题。

搜索每个岛屿在淹没后的情况，判断连通块，注意一块岛屿淹没后有可能变成两块，不要直接判断连通块。

算法流程：

1. 找到一个陆地。
2. 广搜遍历连通块。
3. 修改岛屿。
4. 再次广搜判断是否增加或减少。

如下：

.........
.##...##.
.#######.
.##...##.
.........

代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[1007][1007], b[1007][1007], ca = 0, cnta = 0, ans = 0, via[1007][1007], v[100007];
char ch;
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
inline void dfsa(int x, int y) {
    if (via[x][y] == 0)
        ca++, via[x][y] = ++cnta;

    fr(4) {
        int tx = x + dx[i], ty = y + dy[i];

        if (a[tx][ty] == 1 && 1 < tx && tx < n && 1 < ty && ty < n && !via[tx][ty]) {
            via[tx][ty] = via[x][y];
            dfsa(tx, ty);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> ch;

            if (ch == '#')
                a[i][j] = 1;
        }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] && via[i][j] == 0)
                dfsa(i, j);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] == 1)
                if (a[i - 1][j] == 1 && a[i + 1][j] == 1 && a[i][j - 1] == 1 && a[i][j + 1] == 1)
                    b[i][j] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (b[i][j] == 1 && via[i][j])
                v[via[i][j]] = 1;

    for (int i = 1; i <= cnta; i++) {
        ans += (v[i] == 1);
    }

    cout << ca - ans << endl;
    return 0;
}