#6#8#10RE 求助!在线招唤神犇!(bfs)
查看原帖
#6#8#10RE 求助!在线招唤神犇!(bfs)
583916
tjer楼主2022/2/11 19:20
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int sum=0,m,n,a[1001][1001]={},v[1001][1001]={};
int f[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct rode{
	int ex,ey; 
};
void bfs(){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]!=0&&v[i][j]==0){
				int head=1,tail=1;
				struct rode q[101];
				q[tail].ex=i;
				q[tail].ey=j;
				a[i][j]=0;
				v[i][j]=1;
				tail++;
			while(head<tail){
				for(int i=0;i<=3;i++){
					int tx=q[head].ex+f[i][0];
					int ty=q[head].ey+f[i][1];
					if(tx<0||tx>m||ty<0||ty>n) continue;
					if(a[tx][ty]!=0){
						v[tx][ty]=1;
						q[tail].ex=tx;
						q[tail].ey=ty;
						a[tx][ty]=0;
						tail++;
							}
						}
					head++;
				}
			sum++;
			}else{
				continue;
			}
		}
	}
}
int main () {
	cin >>m >>n;
	for(int i=1;i<=m;i++){
		char x[maxn];
		cin >>x;
		for(int j=1;j<=n;j++){
			a[i][j]=x[j-1]-'0';
		}
	}
	bfs();
	cout <<sum;
	return 0;
}


2022/2/11 19:20
加载中...