BFS24pts求助
查看原帖
BFS24pts求助
1228017
xiaomiao_001楼主2025/2/8 11:02
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <cstdio>
using namespace std;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,vis[1005][1005];
bool Imap[1050][1005],iMap[1005][1005];
int ans;
char a[1005][1005];

struct node{
	int x,y;
};
queue<node> q; 
void bfs(){
	ans++;
	while(!q.empty()){
		int xx=q.front().x;
		int yy=q.front().y;
		vis[xx][yy]=1;
		q.pop();
		for(int i=0;i<4;i++){
			int x1=xx+dx[i];
			int y1=yy+dy[i];
			if(x1>=1 && y1>=1 && x1<=n && y1<=n){
				if(Imap[x1][y1] && !vis[x1][y1]){
					q.push({x1,y1});
				}
			}
		}
		
	}
}
int Howmany(){
	memset(vis,0,sizeof(vis));
	ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(Imap[i][j]!=0 && vis[i][j]==0){
				q.push({i,j});
				bfs();
			}
		}
	}	
	return ans;	
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a[i];
		for(int j=0;j<n;j++){
			if(a[i][j]=='.'){
				Imap[i][j+1]=0;
			}
			else{
				Imap[i][j+1]=1;
			}
		}
	}
	int cnt1=Howmany();
	for(int i=0;i<=n+1;i++){
		Imap[i][0]=0;
		Imap[i][n+1]=0;
		Imap[0][i]=0;
		Imap[n+1][i]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if((!Imap[i+1][j] || !Imap[i-1][j] || !Imap[i][j+1] || !Imap[i][j-1]) && Imap[i][j]){
				iMap[i][j]=0;
			}
			else if(Imap[i][j]==0){
				iMap[i][j]=0;
			}
			else{
				iMap[i][j]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			Imap[i][j]=iMap[i][j]; 
		}
	}
	int cnt2=Howmany();
	cout<<cnt1-cnt2;
	return 0;
}
2025/2/8 11:02
加载中...