bfs12分求助
查看原帖
bfs12分求助
845691
cyz_czy楼主2023/5/21 12:24
#include <iostream>
#include <queue>

const int N=1e3+1e1;

bool l[N][N];
bool p[N][N];

int m;
int c;

void input(){
	scanf("%d",&m);
	
	char a;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++){
			
			std::cin>>a;
			if(a=='#')
				l[i][j]=true;
		}
		
	return ;
}

struct st{
	int x,y;
};

std::queue<st> q;

const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};

void bfs(){
	while(!q.empty()){
		int tx=q.front().x;
		int ty=q.front().y;
		
		p[tx][ty]=true;
		
		q.pop();
		
		bool a=false;
		
		for(int i=0;i<4;i++){
					
			int tempx=tx+dx[i];
			int tempy=ty+dy[i];
					
			if(tempx<1||tempx>m||tempy<1||tempy>m)
				continue;
					
			if(!l[tempx][tempy])
				a=true;
		}
		
		if(!a)
			c++;
		
		for(int i=0;i<4;i++){
			
			int tempx=tx+dx[i];
			int tempy=ty+dy[i];
			
			if(tempx<1||tempx>m||tempy<1||tempy>m||!l[tempx][tempy]||p[tempx][tempy])
				continue;
				
			q.push(st{tempx,tempy});
			
			p[tempx][tempy]=true;
		}
	}
	
	while(!q.empty())
		q.pop();
	
	return ;
}

int main(){
	input();
	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			if(l[i][j]&&!p[i][j])
				q.push(st{i,j}),bfs();
	
	printf("%d",c);
	
	return 0;
}
2023/5/21 12:24
加载中...