2018年第九届蓝桥杯第九题：全球变暖（满分23分）

标题：全球变暖

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

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

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

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

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

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

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

【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。

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

【输出格式】
一个整数表示答案。

【输入样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......

【输出样例】
1

思路：联通成分标记

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string.h>
  4 #include <string>
  5 using namespace std;
  6 const int N = 10002;
  7 int a[N][N] = {0};
  8 int b[N][N] = {0};
  9 int c[N][N] = {0};
 10 string str[N];
 11 void label(int a[N][N],int i,int j,int p)
 12 {
 13     a[i][j] = p;
 14     if(a[i+1][j]==-1){
 15         label(a,i+1,j,p);
 16     }
 17     if(a[i-1][j]==-1){
 18         label(a,i-1,j,p);
 19     }
 20     if(a[i][j+1]==-1){
 21         label(a,i,j+1,p);
 22     }
 23     if(a[i][j-1]==-1){
 24         label(a,i,j-1,p);
 25     }
 26 }
 27 int label(int a[N][N],int n)
 28 {
 29     int p = 0;
 30     for(int i=1;i<=n;i++){
 31         for(int j=1;j<=n;j++){
 32             if(a[i][j]==-1){
 33                 p++;
 34                 label(a,i,j,p);
 35             }
 36         }
 37     }
 38     return p;
 39 }
 40 void print_a(int a[N][N],int n)
 41 {
 42     for(int i=1;i<=n;i++){
 43         for(int j=1;j<=n;j++){
 44             printf("%2d ",a[i][j]);
 45         }
 46         printf("
");
 47     }
 48 }
 49 void erode(int a[N][N],int b[N][N],int n)
 50 {
 51     for(int i=1;i<=n;i++){
 52         for(int j=1;j<=n;j++){
 53             if(a[i][j]==0){
 54                 b[i-1][j] = 0;
 55                 b[i+1][j] = 0;
 56                 b[i][j-1] = 0;
 57                 b[i][j+1] = 0;
 58             }
 59         }        
 60     }    
 61 }
 62 int main()
 63 {
 64     int n;
 65     freopen("data.in","r",stdin);
 66     scanf("%d",&n);
 67     for(int i=1;i<=n;i++){
 68         cin>>str[i];
 69         cout<<str[i]<<endl;
 70     }
 71     
 72     for(int i=1;i<=n;i++){
 73         for(int j=1;j<=n;j++){
 74             char c = str[i][j-1];
 75             if(c=='#')
 76                 a[i][j] = -1;
 77             else
 78                 a[i][j] = 0;        
 79         }
 80     }
 81     memcpy(b,a,sizeof(a));
 82     memcpy(c,a,sizeof(a));
 83     print_a(a,n);
 84     int n1;
 85     cout<<(n1=label(a,n))<<endl;    
 86     print_a(a,n);
 87     erode(b,c,n);
 88     printf("
");
 89     print_a(c,n);
 90     int n2;
 91     cout<<(n2=label(c,n))<<endl;
 92     cout<<n1-n2;
 93     return 0;
 94 }
 95 
 96 // 用字符读取会出现缓冲区读无效字符问题 
 97 //    char c;
 98 //    for(int i=1;i<=n;i++){
 99 //        for(int j=1;j<=n;j++){
100 //            scanf("%c",&c);
101 //            if(c=='#')
102 //                a[i][j] = -1;
103 //            else
104 //                a[i][j] = 0;        
105 //        }
106 //        scanf("%c",&c);
107 //    } 
108 
109 
110 
111

连通分量标记

2018年第九届蓝桥杯 第九题：全球变暖（满分23分）

2018年第九届蓝桥杯第九题：全球变暖（满分23分）