全球变暖（蓝桥杯 2018 年第九届省赛）

题目描述

你有一张某海域 N×N 像素的照片，. 表示海洋、 # 表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

其中 "上下左右" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......
.......
.......
.......
....#..
.......
.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数 N。(1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出格式

一个整数表示答案。

输入输出样例

输入 

7 
.......
.##....
.##....
....##.
..####.
...###.
.......  

输出 

1

说明/提示

时限 1 秒, 256M。

//代码如下:

//全球变暖问题的本质是:
//寻找连通块 遍历连通块 在连通块的范围内寻找一块陆地（就够了，足以证明整个连通块不会被淹没） 
//记得将整个连通块寻找完全 建议使用dfs搜索#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>using namespace std;
//存储图
vector<string> picture;
//访问数组
vector<vector<bool>>  visited;
//方位数组
int indexx[]={0,0,-1,1};
int indeyy[]={-1,1,0,0};
//图的边长
int N; 
//标志整个连通块是不是被淹没
bool flag; 
//存储坐标
typedef struct Node{int x;int y;Node(int x,int y):x(x),y(y){}
}Node; 
//存储没有被淹没的连通块
int ans=0; void dfs(int x,int y){//剪枝操作if(x<0||x>N||y<0||y>N||visited[x][y]||picture[x][y]!='#') return;//每次只处理一个陆地 if(!flag){int cnt=0;for(int i=0;i<4;i++){int newx=x+indexx[i];int newy=y+indeyy[i];if(0<=newx&&newx<N&&0<=newy&&newy<N&&picture[newx][newy]=='#') {cnt++;}}if(cnt==4){//整个连通块不可能被淹没 flag=true;ans++;}	//将处理过的连通块中的一部分陆地标记 }//继续处理连通块知道整个连通块都被搜索出来 visited[x][y]=true;for(int i=0;i<4;i++){int newx=x+indexx[i];int newy=y+indeyy[i];if(newy<0||newy>N||newy<0||newy>N||visited[newx][newy]||picture[newx][newy]!='#')continue;dfs(newx,newy);}//直到整个连通块都被处理掉 return ;
}
int main(){//图的边长 cin>>N;//存储图 for(int i=0;i<N;i++) {string ss;cin>>ss;picture.push_back(ss);}//存储被访问数组 for(int i=0;i<N;i++){vector<bool> ss(N,false);visited.push_back(ss);}//遍历整张图 //记录开始岛屿数量int rans=0;for(int row=0;row<N;row++){for(int col=0;col<N;col++){//记录这个位置 //继续寻找下一个连通块 if(picture[row][col]=='#'&&!visited[row][col]){rans++;flag=false;dfs(row,col);}}}//输出答案 cout<<rans-ans<<endl;return 0;
}
/*
5
.....
.###.
.###.
.###.
.....9
.........
.#######.
.#######.
.#######.
..#.#....
.#######.
.#######.
.#######.
.........
*/