简单Flood fill

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
//#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
typedef long long LL;
typedef pair<int, int> PII;

int n;
char g[N][N];
bool st[N][N];
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

bool bfs(int a, int b)
{
    bool res = false;
    queue<PII> q;
    q.push({ a, b });
    st[a][b] = true;

    while (!q.empty()) {
        auto t = q.front(); q.pop();
        int fx = 0;
        for (int i = 0; i < 4; i++) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x < 0 or x >= n or y < 0 or y >= n) {
                fx++;
            }
            else if (x >= 0 && x < n && y >= 0 && y < n && g[x][y] == '#') {
                fx++;
                if (!st[x][y]) {
                    st[x][y] = true;
                    q.push({ x, y });
                }
            }
        }
        if (fx == 4) res = true;
    }

    return res;
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%s", g[i]);
    }

    memset(st, false, sizeof st);

    int cnt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == '#' && !st[i][j]) {
                cnt++;  // 原岛屿数量
                if (bfs(i, j))
                    ans++;  // 未被完全淹没的岛屿数量
            }
        }
    }

    printf("%d\n", cnt - ans);

    return 0;
}