题目描述

写这题的时候有点不清醒，条件判断的时候||写成&&调了半天。。
这题明显岛屿可以看成联通块，边跑边判断当前点陆地是否四周存在海
比较裸的一道题吧

样例

//很明显每块岛屿是一个联通块，可以dfs跑联通块暴力解
#include<bits/stdc++.h>
using namespace std;
const int N=1002;
char g[N][N];
int n,vis[N][N],f;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1}; 
int ans=0,f1=0,id=0;
void dfs(int x,int y){
    vis[x][y]=1;
    if(ans==0){ 
    for(int i=0;i<4;i++){//搜索四个点看看不是存在不会被淹没的陆地 
        int p=x+dx[i];
        int q=y+dy[i];
        if(vis[p][q]||g[p][q]=='#')//如果周围的点已经被访问或者是陆地的话(已经访问过的点必定之前是陆地) 
        {
            f1++;//周围四个点都是陆地那么加1 
        }   
    } 
//  cout<<f1<<'\n';
    if(!f&&f1==4){//f1等于4则存在不被淹的陆地 
        ans=1;//ans=1说明这块联通块不会被完全淹没
        f=1;
    }
    f1=0;
    } 
    for(int i=0;i<4;i++){
        int p=x+dx[i];
        int q=y+dy[i];
        if(p<0||q<0||p>=n||q>=n)
            continue ;
        if(!vis[p][q]&&g[p][q]=='.')//如果周围一开始就是海
            continue ;
        g[x][y]='.';//图边跑边删
        if(!vis[p][q]&&g[p][q]=='#'){
            dfs(p,q);
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>g[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(g[i][j]=='.'||vis[i][j])//找联通块
                continue;
            dfs(i,j);
            if(!ans)//ans=0说明岛屿被完全淹没
                id++;
            f=f1=ans=0;//每次dfs都要初始化
        }
    }
    cout<<id;
}