蓝桥杯2018年第九届真题-全球变暖 (C++ AC代码)

解题思路:

题目问的是最终有多少个岛屿会被淹没，而题目又告诉我们：

**如果一块陆地四周都是海，则这块陆地会被淹没。**
我们可以这样理解：

**如果这块岛屿中存在一个点四周都是陆地‘#’，则这个岛屿一定不会被淹没。**
转换成这个思想之后问题就好解决了

        刚开始还是之前的联通块套路，**dfs搜索连在一块的岛屿并标记，每搜索一次证明存在的岛屿数+1，在搜索的过程中我们需要看看是否存在这样的点（四周都是‘#’），如果存在，我们就把flag置为0，不存在置为1，然后每搜索完一大块岛屿之后答案数+flag就可以了。**



参考代码:

#include <iostream>
#include <stdio.h>
using namespace std;
char a[1001][1001],book[1001][1001];//a存储地图  book为标记数组  
int next1[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//枚举下一步搜索操作
int N,flag,ans=0;//flag为标志变量 如果存在四周都是#的点 标记为0 如果不存在 标记为1 
void dfs(int x,int y) //搜索岛屿 
{ int i,tx,ty;
  for(i=0;i<4;i++)
   { tx=x+next1[i][0];
     ty=y+next1[i][1];
     if(tx<1||ty<1||ty>N||tx>N) continue;//边界情况处理 
     if(!book[tx][ty]&&a[tx][ty]=='#')
     { book[tx][ty]=1; //标记这个点 
        if(flag&&tx+1>=1&&ty+1>=1&&tx+1<=N&&ty+1<=N&&a[tx][ty+1]=='#'&&a[tx][ty-1]=='#'&&a[tx+1][ty]=='#'&&a[tx-1][ty]=='#')
        flag=0; //如果存在四周都是#的点，证明这个岛屿不会被淹没 
       dfs(tx,ty);
     }
   }
}
int main()
{  
    cin>>N;
    int i,j;
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
         cin>>a[i][j];//输入地图 
    for(i=1;i<=N;i++)
     for(j=1;j<=N;j++)
     { if(a[i][j]=='#'&&!book[i][j])//开始从这个点搜索这个岛屿 
       { book[i][j]=1;
         flag=1;//先默认不存在四周都是#这样的点 
         dfs(i,j);
         ans+=flag;//如果搜索完成后还是不存在，则这个岛屿一定会淹没，加到结果里 
       }
     }
     printf("%d",ans);
    return 0;
}