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; }
信息
- ID
- 441
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 128
- 已通过
- 35
- 上传者