_xiao_ @ 2023-08-22 16:05:04
#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;
}by myzzym @ 2023-08-22 16:22:25
??是超时原因还是答案错误？不敢交上去
by myzzym @ 2023-08-22 16:23:02
其实只要看看每个岛屿旁边有没有海洋就可以了，没有海洋就ans++，最后输出ans，没那么复杂
by Skii1y @ 2023-08-22 16:38:11
#include<bits/stdc++.h>
using namespace std;
int x[5]={0,0,1,-1},y[5]={1,-1,0,0};
char m[1001][1001],a;
int main(){
long long n,sl=0,al=0,h=0;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a;
m[i][j]=a;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
h=0;
if(m[i][j]=='#'){
al++;
m[i][j]='p';
long long que[10001][3],tail=1,head=1,u,v;
que[1][1]=i;
que[1][2]=j;
while(head<=tail){
for(int k=0;k<=3;k++){
u=x[k]+que[head][1];
v=y[k]+que[head][2];
if(m[u][v]=='#'&&u>0&&u<=n&&v>0&&v<=n){
if(m[u][v+1]!='.'&&m[u][v-1]!='.'&&m[u+1][v]!='.'&&m[u-1][v]!='.'){
h=1;
}
tail++;
que[tail][1]=u;
que[tail][2]=v;
m[u][v]='p';
}
}
head++;
}
if(h==1){
sl++;
}
}
}
}
cout<<al-sl;
return 0;
}思路和myzzym是一样的，这里出示代码以供参考（勿抄）
by Ekin123 @ 2024-09-04 21:15:52
668899寄