BFS,50分求调
查看原帖
BFS,50分求调
866487
zrx114楼主2023/8/10 20:19
#include<bits/stdc++.h>
using namespace std;
int m,n;
char g[105][105];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int queues[10005][2];
void BFS(int x,int y){
	int head=0,tail=1;
	queues[tail][0]=x;
	queues[tail][1]=y;
	g[x][y]='0';
	do{
		head++;
		for(int i=0;i<4;i++){
			int newx=queues[head][0]+dx[i];
			int newy=queues[head][1]+dy[i];
			if(g[newx][newy]>='1' && g[newx][newy]<='9'){
				tail++;
				queues[tail][0]=newx;
				queues[tail][1]=newy;
				g[newx][newy]='0';
			}
		}
	}while(head<tail);
}
int main(){
	cin>>m>>n;
	cin.ignore();
	for(int i=1;i<=m;i++){
		string line;
		getline(cin,line);
		for(int j=0;j<n;j++){
			g[i][j+1]=line[j];
		}
	}
	int cnt=0;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(g[i][j]>='1' && g[i][j]<='9'){
				BFS(i,j);
				cnt++;
			}
		}
	}
	cout<<cnt;
	return 0;
}

看一下午了qwq

2023/8/10 20:19
加载中...