社区讨论
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 条回复,欢迎继续交流。
正在加载回复...