第九届其他题目解析链接

 

第九题  全球变暖


标题：全球变暖

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

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

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

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

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

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

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

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

【输出样例】
1

 

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms

这个题  dfs或者bfs都可以

但是有个坑需要注意下

首先我们很容易想到一个方法 

先遍历一遍 遇到 # 进行BFS   统计有几个岛屿

然后把挨着水的置为0  

再遍历一遍 BFS统计还剩多少岛屿

两次统计结果相减就是答案

注意这个做法是不对的   因为一个岛屿水升高后可能变成两个岛屿了！

比如下面这两组测试数据

9
.........
.###.###.
.#######.
.###.###.
.........
..##.###.
..##.###.
.....###.
.........

本来有三个岛屿
水上升后还有三个岛屿  但是有一个岛屿被淹没了

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 # # 0 # # 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 # 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

7
.......
.#...#.
.#.###.
...###.
.#####.
...#...
.......
淹没后 如下  如果你此时再去dfs/bfs 判断的话  会判断出存在两个岛屿 
初始也是两个岛屿 所以会得到错误答案 淹没0个
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 # 0 0
0 0 0 # 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

所以 这道题我的做法是 

先转换   . 用0表示    #用1表示   用5代表被淹没的地方

先遍历一遍 把挨着水的位置标记一下（赋值为5）

然后遍历一遍 遇到5的话 就拿5去BFS 看5是否和1联通着 若联通  就说明并没有完全淹没这个岛屿

并且把5的联通块赋值为0   同时计数

我也不知道我的对不对 （因为没地方交题）  不过从思路上来讲  解决了淹没后变两个岛屿的问题

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1e3+7;
int a[maxn][maxn];
typedef struct{
    int x1,y1;
}node;
int cnt;
void bfs(int x,int y){
    int flag=0;//flag用来标记是否与1联通
    node q[100000];
    int w=0,t=0;
    q[w].x1=x; q[w].y1=y; a[x][y]=0; w++;
    while(t!=w){
        int x2=q[t].x1,y2=q[t].y1;
        if(a[x2+1][y2]!=0){
            if(a[x2+1][y2]==1)flag=1;
            else {q[w].x1=x2+1; q[w].y1=y2; a[x2+1][y2]=0; w++;}
        }
        if(a[x2-1][y2]!=0){
            if(a[x2-1][y2]==1)flag=1;
            else {q[w].x1=x2-1; q[w].y1=y2; a[x2-1][y2]=0; w++;}
        }
        if(a[x2][y2+1]!=0){
            if(a[x2][y2+1]==1)flag=1;
            else {q[w].x1=x2; q[w].y1=y2+1; a[x2][y2+1]=0; w++;}
        }
        if(a[x2][y2-1]!=0){
            if(a[x2][y2-1]==1)flag=1;
            else {q[w].x1=x2; q[w].y1=y2-1; a[x2][y2-1]=0; w++;}
        }
        t++;
    }
    if(flag==0)cnt++;
}
int n;
char ch;
int main(){
    scanf("%d",&n);getchar();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%c",&ch);
            if(ch=='#')a[i][j]=1;
        }getchar();
    }

    for(int i=1;i<n-1;i++){
        for(int j=1;j<n-1;j++){
            if(a[i][j]==1){
                if(a[i+1][j]==0||a[i-1][j]==0||a[i][j-1]==0||a[i][j+1]==0){
                    a[i][j]=5;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ",a[i][j]);
        }printf("\n");
    }
    for(int i=1;i<n-1;i++){
        for(int j=1;j<n-1;j++){
            if(a[i][j]==5)bfs(i,j);//BFS  5的联通块
        }
    }
    printf("%d\n",cnt);
}