1 条题解

  • 0
    @ 2024-12-5 12:25:26

    100分代码:

    #include <bits/stdc++.h>
    using namespace std;
    int n = 10, m = 10;  // 固定为10x10,但可以根据需要调整
    vector<vector<int>> a;   // 用 vector 实现动态数组
    vector<vector<int>> vis; // 访问标记数组
    int cnt = 0;
    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    struct node {
        int x, y;
    };
    // 广度优先搜索,标记从边界开始的空白区域
    void bfs(int x0, int y0) {
        a[x0][y0] = 1;
        vis[x0][y0] = 1;
        queue<node> q;
        q.push({x0, y0});
        while (!q.empty()) {
            node curr = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dir[i][0];
                int ny = curr.y + dir[i][1];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0 && vis[nx][ny] == 0) {
                    vis[nx][ny] = 1;
                    a[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    // 计算内部分隔的区域
    void bfs_cnt(int x0, int y0) {
        vis[x0][y0] = 1;
        cnt++;
        queue<node> q;
        q.push({x0, y0});
        while (!q.empty()) {
            node curr = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dir[i][0];
                int ny = curr.y + dir[i][1];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0 && vis[nx][ny] == 0) {
                    vis[nx][ny] = 1;
                    q.push({nx, ny});
                    cnt++;
                }
            }
        }
    }
    int main() {
        // 初始化动态数组
        a.resize(n + 1, vector<int>(m + 1, 0));
        vis.resize(n + 1, vector<int>(m + 1, 0));
        // 输入数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }
        // 从上下边界进行BFS标记外部区域
        for (int j = 1; j <= m; j++) {
            if (a[1][j] == 0) bfs(1, j);
            if (a[n][j] == 0) bfs(n, j);
        }
        // 从左右边界进行BFS标记外部区域
        for (int i = 1; i <= n; i++) {
            if (a[i][1] == 0) bfs(i, 1);
            if (a[i][m] == 0) bfs(i, m);
        }
        // 对内部的0进行计数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] == 0 && vis[i][j] == 0) {
                    bfs_cnt(i, j);
                }
            }
        }
        cout << cnt << endl;
        return 0;
    }
    
    
    • 1

    信息

    ID
    837
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    15
    已通过
    4
    上传者