全球变暖蓝桥杯2018省赛真题

全球变暖蓝桥杯2018省赛真题

DFS大法

全球变暖

#include <bits/stdc++.h>
using namespace std;
#define int long long
bool flag;
char a[1010][1010];
int cnt,n,ans=0,pre_ans=0,d[4][2]= {1,0,-1,0,0,1,0,-1};
void dfs(int x,int y){
    if(x>=n||x<0||y>=n||y<0||a[x][y]!='#')return;
    if(flag==false){
        cnt=0;
        for(int i=0; i<4; i++){
            int tx=x+d[i][0],ty=y+d[i][1];
            if(tx<n&&tx>=0&&ty<n&&ty>=0&&a[tx][ty]!='.')cnt++;
        }
        if(cnt==4){
            ans++;//最后不会被淹没的点+1
            flag=true;//当前岛屿是不可以被淹没的
        }
    }
    a[x][y]='*';//已经探索的岛屿标记成'*'
    for(int i=0; i<4; i++){
        int tx=x+d[i][0],ty=y+d[i][1];
        dfs(tx,ty);
    }
}
signed main(){
    cin>>n;
    for(int i=0; i<n; i++)cin>>a[i];//注意输入的是字符串
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)//如被找到是同一岛则会被标*,不回溯，只有#才是未被搜索的岛屿的一角
            if(a[i][j]=='#'){
                pre_ans++;//那么岛屿数目加1
                flag=false;//假设会淹没
                dfs(i,j);//回溯标记这个岛屿的所有点的坐标，并且如果不会被完全的淹没，那么就标记
            }
    cout<<pre_ans-ans;//原始的岛屿数-剩下岛屿数=被淹没岛屿数
}