60分BFS求调
查看原帖
60分BFS求调
864183
Jasper20222022楼主2024/4/7 19:36
#include <iostream>
#include <queue> 
using namespace std;
struct zb{
	int xz,yz; 
};
bool s[102][102];//0代表有水,1代表没水 
bool bl[102][102];//0没去,1去过 
queue<zb> q;
int n,m;
void bfs(int x,int y){
	zb xx;
	xx.xz=x;
	xx.yz=y;
	q.push(xx);
	bl[x][y]=1;
	while(q.size()>0){
		zb r=q.front();
		x=inttni.xz;
		y=inttni.yz;
		if(s[x+1][y]==0 && (x+1)<=n && bl[x+1][y]==0){
			zb w;
			w.xz=x+1;
			w.yz=y;
			q.push(w);
			bl[x+1][y]=1;
		}
		if(s[x-1][y]==0 && (x-1)>0 && bl[x-1][y]==0){
			zb w;
			w.xz=x-1;
			w.yz=y;
			q.push(w);
			bl[x-1][y]=1;
		}
		if(s[x][y+1]==0 && (y+1)<=n && bl[x][y+1]==0){
			zb w;
			w.xz=x;
			w.yz=y+1;
			q.push(w);
			bl[x][y+1]=1;
		}
		if(s[x][y-1]==0 && (y-1)>0 && bl[x][y-1]==0){
			zb w;
			w.xz=x;
			w.yz=y-1;
			q.push(w);
			bl[x][y-1]=1;
		}
		if(s[x-1][y-1]==0 && (y-1)>0 && (x-1)>0 && bl[x-1][y-1]==0){
			zb w;
			w.xz=x-1;
			w.yz=y-1;
			q.push(w);
			bl[x-1][y-1]=1;
		}
		if(s[x+1][y-1]==0 && (y-1)>0 && (x+1)<=n && bl[x+1][y-1]==0){
			zb w;
			w.xz=x+1;
			w.yz=y-1;
			q.push(w);
			bl[x+1][y-1]=1;
		}
		if(s[x-1][y+1]==0 && (y+1)<=n && (x-1)>0 && bl[x-1][y+1]==0){
			zb w;
			w.xz=x-1;
			w.yz=y+1;
			q.push(w);
			bl[x-1][y+1]=1;
		}
		if(s[x+1][y+1]==0 && (y+1)<=n && (x+1)<=n && bl[x+1][y+1]==0){
			zb w;
			w.xz=x+1;
			w.yz=y+1;
			q.push(w);
			bl[x+1][y+1]=1;
		}
		q.pop(); 
	}
}
int main(){
	int sum=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char S;
			cin>>S;
			s[i][j]=(S=='.');
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]==0 && bl[i][j]==0){
				bfs(i,j);
				sum++;
			}
		}
	}
	cout<<sum;
	return 0;
} 

(100行代码大吉)

2024/4/7 19:36
加载中...