信息学奥赛一本通T1329-细胞

解题思路:BFS

注意事项:

参考代码:

#include<iostream>
#include<queue>
using namespace std;
const int N = 1e3 +10;
char a[N][N];
int n,m,cnt;
bool v[N][N];
struct node{
	int x, y;
};
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
queue<node> q;
void bfs(int x, int y){
	q.push(node{x,y});
	v[x][y] = true;
	while(!q.empty()){
		node nd = q.front();
		q.pop();
		for(int i = 0; i < 4; i ++){
			int nx = nd.x + d[i][0];
			int ny = nd.y + d[i][1];
			if(nx >= 0 && nx < n && ny >= 0 && ny < m && !v[nx][ny] && a[nx][ny] != '0'){
				v[nx][ny] = true;
				q.push(node{nx,ny});
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m; j ++)
			cin >> a[i][j];
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m; j ++)
			if(!v[i][j] && a[i][j] != '0') {
				bfs(i,j);
				cnt ++;
			}
	cout << cnt;
	return 0;
}