http://tjuacm.chaosheng.top/problem.php?id=1283
https://www.luogu.com.cn/problem/P1451
思路参考 https://www.luogu.com.cn/blog/user20651/solution-p1451
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 410; int n, m, cnt; int matrix[N][N]; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; struct cell{ int x, y; }; void bfs(int x, int y){ queue<cell> q; cell f, v; f.x = x; f.y = y; matrix[f.x][f.y] = 0; q.push(f); cnt++; while(!q.empty()){ f = q.front(); q.pop(); for(int i = 0; i < 4; i++){ v.x = f.x + dx[i]; v.y = f.y + dy[i]; if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < m && matrix[v.x][v.y] == 1) { matrix[v.x][v.y] = 0; q.push(v); } } } } int main(){ string s; while(cin >> n >> m){ for(int i = 0; i < n; i++){ cin >> s; for(int j = 0; j < m; j++){ if(s[j] != '0') matrix[i][j] = 1; else matrix[i][j] = 0; } } cnt = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(matrix[i][j] == 1) bfs(i, j); } } printf("%d\n", cnt); } return 0; }