蒟蒻36分求助
查看原帖
蒟蒻36分求助
569666
ooooo1楼主2023/1/10 14:32
#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
bool b[1005][1005],c[1005][1005];
int n;
int ans=0;
int fx[5][5]{{1,0},{0,1},{-1,0},{0,-1}};
bool in(int x,int y){
	return x>=0&&x<n&&y>=0&&y<n;
}
void dfs(int sx,int sy){
	b[sx][sy]=1;
	for(int i=0;i<4;i++){
		int xx=sx+fx[i][0];
		int xy=sy+fx[i][1];
		
		if(in(xx,xy)&&b[xx][xy]==0&&a[xx][xy]=='#'){
			dfs(xx,xy);
		}
	}
	return;
}
void dvs(int sx,int sy){
	c[sx][sy]=1;
	for(int i=0;i<4;i++){
		int zx=sx+fx[i][0];
		int zy=sy+fx[i][1];
		if(in(zx,zy)&&!c[zx][zy]&&a[zx][zy]=='#'){
			dvs(zx,zy);
		}
	}
}
int main(){
	
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>a[i][j];
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]=='#'&&b[i][j]==0){
				dfs(i,j);
				ans++;
				
			}
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<4;k++){
				int xx=i+fx[k][0];
				int xy=j+fx[k][1];
				if(a[xx][xy]=='.'&&!b[xx][xy]){
					a[i][j]='.';
				}
			}
		}
	
	}

	int ans1=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]=='#'&&c[i][j]==0){
				dvs(i,j);
				ans1++;
			}
		}
	}

	cout<<ans-ans1;
    return 0;
}

2023/1/10 14:32
加载中...