题解 | 没挡住洪水

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 1010;
char str[N][N];      
bool will_sink[N][N]; 
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool visited[N][N];   

bool is_fully_sunk(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = true;
    bool all_sunk = true;

    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();

        if (!will_sink[cx][cy]) {
            all_sunk = false;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && 
                str[nx][ny] == '#' && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return all_sunk;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            str[i][j] = s[j-1];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (str[i][j] == '#') {
                for (int k = 0; k < 4; k++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if (ni >= 1 && ni <= n && nj >= 1 && nj <= n && str[ni][nj] == '.') {
                        will_sink[i][j] = true;
                        break; 
                    }
                }
            }
        }
    }

    int ans = 0;
    memset(visited, 0, sizeof visited);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (str[i][j] == '#' && !visited[i][j]) {
                if (is_fully_sunk(i, j)) {
                    ans++;
                }
            }
        }
    }

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