2 条题解

  • 0
    @ 2026-6-13 11:23:32
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
            cin.tie(nullptr);
                freopen("boom.in", "r", stdin);
                    freopen("boom.out", "w", stdout);
    
                        int n, m;
                            cin >> n >> m;
                                vector<string> g(n);
                                    for (int i = 0; i < n; ++i) cin >> g[i];
    
                                        vector<int> row(n), col(m);
                                            for (int i = 0; i < n; ++i) {
                                                    for (int j = 0; j < m; ++j) {
                                                                if (g[i][j] == '1') {
                                                                                ++row[i];
                                                                                                ++col[j];
                                                                                                            }
                                                                                                                    }
                                                                                                                        }
    
                                                                                                                            vector<int> rvis(n), cvis(m);
                                                                                                                                int ans = 0;
                                                                                                                                    for (int i = 0; i < n; ++i) {
                                                                                                                                            for (int j = 0; j < m; ++j) {
                                                                                                                                                        if (g[i][j] != '1' || rvis[i] || cvis[j]) continue;
                                                                                                                                                                    ++ans;
                                                                                                                                                                                queue<pair<int,int>> q;
                                                                                                                                                                                            q.push({i, j});
                                                                                                                                                                                                        rvis[i] = cvis[j] = 1;
                                                                                                                                                                                                                    while (!q.empty()) {
                                                                                                                                                                                                                                    auto [x, y] = q.front(); q.pop();
                                                                                                                                                                                                                                                    for (int k = 0; k < m; ++k) {
                                                                                                                                                                                                                                                                        if (g[x][k] == '1' && !cvis[k]) {
                                                                                                                                                                                                                                                                                                cvis[k] = 1;
                                                                                                                                                                                                                                                                                                                        q.push({x, k});
                                                                                                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                                                                                                                            }
                                                                                                                                                                                                                                                                                                                                                                            for (int k = 0; k < n; ++k) {
                                                                                                                                                                                                                                                                                                                                                                                                if (g[k][y] == '1' && !rvis[k]) {
                                                                                                                                                                                                                                                                                                                                                                                                                        rvis[k] = 1;
                                                                                                                                                                                                                                                                                                                                                                                                                                                q.push({k, y});
                                                                                                                                                                                                                                                                                                                                                                                                                                                                    }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            }
    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                cout << ans << '\n';
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    return 0;
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    }
    

    信息

    ID
    441
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    128
    已通过
    35
    上传者