2 条题解
-
0
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
#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
- 上传者