Submission #74279603

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second

const int N = 1010;
// 四个方向：上下左右
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, m;          // n=行数，m=列数
int a[N][N];       // a[i][j]=1表示黑色(#)，0表示白色(.)
bool v[N][N];      // 标记是否已访问

// BFS遍历连通区域，返回1表示该区域被完全包围，0表示接触边缘
int bfs(int x, int y) {
    queue<pii> q;
    q.push({x, y});
    v[x][y] = true;
    // flag=1表示初始认为被包围，若接触边缘则置为0
    bool flag = true;

    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        int cx = t.fi, cy = t.se;

        // 检查当前单元格是否在网格边缘
        if (cx == 1 || cx == n || cy == 1 || cy == m) {
            flag = 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 <= m && !v[nx][ny] && a[nx][ny] == 0) {
                v[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    return flag ? 1 : 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;  // 直接读整行，避免字符输入的空格问题
        for (int j = 1; j <= m; j++) {
            a[i][j] = (s[j-1] == '#');  // 字符串下标从0开始，网格从1开始
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 未访问 + 白色单元格
            if (!v[i][j] && a[i][j] == 0) {
                ans += bfs(i, j);
            }
        }
    }

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

Submission Info

Judge Result