社区讨论

24分bfs求助

P8662[蓝桥杯 2018 省 AB] 全球变暖参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo1qh1bm
此快照首次捕获于
2023/10/23 01:19
2 年前
此快照最后确认于
2023/11/03 01:58
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int m[1010][1010],a,n;
int dx[5]={-1,0,1,0},dy[5]={0,1,0,-1};
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		char a[11];
		cin>>a;
		for(int j=0;j<n;j++){
			if(a[j]=='#') m[i][j]=1;//岛屿标记为1,否则为0 
		}
	}//输入 
	int sum=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(m[i][j]==1){
				//开始搜索 
				int h[100100][3]={0};
				h[1][1]=i;h[1][2]=j;
				int head=1,tail=1;
				while(head<=tail){
					for(int k=0;k<4;k++){
						int u=h[head][1]+dx[k],v=h[head][2]+dy[k];
						if(u>=0 && u<n && v>=0 && v<n && m[u][v]==1){
							m[u][v]=-1;
							tail++;
							h[tail][1]=u;
							h[tail][2]=v;
						}
					}
					head++;
				}
				//搜索完一个岛屿 
				sum++;
			}
		}
	}//海水还没有上涨时的岛屿数量 
	//cout<<sum<<" ";
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if( abs(m[i+1][j])==1 && abs(m[i-1][j])==1 && abs(m[i][j+1])==1 && abs(m[i][j-1])==1  ){
				m[i][j]=2; 
			}
		}
	}//海水上涨
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(m[i][j]==2){
				//开始搜索 
				int head=1,tail=1;
				int h[100100][3]={0};
				h[1][1]=i;h[1][2]=j;
				while(head<=tail){
					for(int k=0;k<4;k++){
						int u=h[head][1]+dx[k],v=h[head][2]+dy[k];
						if(u>=0 && u<n && v>=0 && v<n && m[u][v]==2){
							tail++;
							m[u][v]=-1;
							h[tail][1]=u;
							h[tail][2]=v;
						}
					}
					head++;
				}
				//搜索完一个岛屿 
				ans++;
			}
		}
	}//海水上涨后的岛屿数量 
	cout<<sum-ans;
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...