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;
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    }
    
    • -1
      @ 2024-8-15 16:44:37
      #include <iostream> #include <algorithm> #include <string> #define SIS std::ios::sync\_with\_stdio(false),cin.tie(0),cout.tie(0) #define endl '\\n' using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const int MAXN = 1e3+5; string s[MAXN]; bool r[MAXN],c[MAXN]; int n,m,ans=0;  void dfs(int x,int y) {     s[x][y]='0';     if(!r[x])     {         r[x]=true;         for(int i=0;i<m;i++)             if(s[x][i]=='1') dfs(x,i);     }     if(!c[y])     {         c[y]=true;         for(int i=0;i<n;i++)             if(s[i][y]=='1') dfs(i,y);     } }  int main() {     SIS;     cin >> n >> m;     for(int i=0;i<n;i++)         cin >> s[i];     for(int i=0;i<n;i++)         for(int j=0;j<m;j++)             if(s[i][j]=='1') dfs(i,j),ans++;     cout << ans << endl;     return 0; }
      
      • 1

      信息

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