题目
标题：全球变暖
【题目描述】
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【样例输入】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【样例输出】
1
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。
代码
1 #include<iostream> 2 #include<string.h> 3 #define N 1005 4 using namespace std; 5 char map[N][N]; 6 int vis[N][N]; 7 int n; 8 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; 9 int count=0; 10 int all_cnt=0; 11 void dfs(int x,int y,int dot){ 12 if(map[x][y]==‘#‘){ 13 all_cnt++; 14 vis[x][y]=dot;//标记 15 for(int i=0;i<n;i++){//检查#是否为边沿 16 int xx=x+dir[i][0]; 17 int yy=y+dir[i][1]; 18 if(!(xx<0||xx>=N||yy<0||yy>=N)&&map[xx][yy]==‘.‘){ 19 count++; 20 break; 21 } 22 } 23 }else{ 24 return; 25 } 26 for(int i=0;i<4;i++){ 27 int xx=x+dir[i][0]; 28 int yy=y+dir[i][1]; 29 if(!(xx<0||xx>=N||yy<0||yy>=N)&&vis[xx][yy]==0){ 30 dfs(xx,yy,dot); 31 } 32 } 33 return; 34 35 } 36 int main(){ 37 cin>>n; 38 for(int i=0;i<n;i++){ 39 for(int j=0;j<n;j++){ 40 cin>>map[i][j]; 41 } 42 } 43 memset(vis,0,sizeof(vis)); 44 int num1=0; 45 int missing_island=0; 46 for(int i=0;i<n;i++){ 47 for(int j=0;j<n;j++){ 48 count=0; 49 all_cnt=0; 50 if(map[i][j]==‘#‘&&vis[i][j]==0){ 51 num1++; 52 dfs(i,j,num1); 53 cout<<all_cnt<<" "<<count<<endl; 54 if(all_cnt==count) 55 missing_island++; 56 } 57 } 58 } 59 cout<<missing_island<<endl; 60 /* 61 for(int i=0;i<n;i++){ 62 for(int j=0;j<n;j++){ 63 cout<<vis[i][j]<<" "; 64 } 65 cout<<endl; 66 }*/ 67 68 69 }
原文：https://www.cnblogs.com/memocean/p/12292394.html