2018年蓝桥杯C/C++ B组省赛试题I：全球变暖题解

r囧r小猫 2022-12-28 14:19 144阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  资源约定
 *  解题思路
 *  解题代码

--------------------

# 题目描述 #

你有一张某海域NxN像素的照片，“。”表示海洋，“＃”表示陆地，如下所示：

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

其中“上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。  
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。  
例如上图中的海域未来会变成如下样子：

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

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

## 输入格式 ##

> 第一行包含一个整数N.（1 <= N <= 1000）  
> 以下N行N列代表一张海域照片。  
> 照片保证第1行，第1列，第N行，第N列的像素都是海洋。

## 输出格式 ##

> 一个整数表示答案。

## 输入样例 ##

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

## 输出样例 ##

## 资源约定 ##

> 峰值内存消耗（含虚拟机）<256M  
> CPU消耗<1000ms

# 解题思路 #

这道题很像《挑战程序设计竞赛》上的“水滩问题”。

要注意这道题最后输出 **被淹没的小岛数量**

我们首先要知道有哪些是小岛，我们认为**只要上下左右相连的就是一个小岛**

那么当我们碰到一个`#`陆地时，我们就对当前这个小岛去做dfs的深搜，我们搜索什么呢？

*  搜索与我们碰到的第一个`#`相连的所有`#`中是否存在一个`#`满足上下左右都是`#`，那么这样的陆地就不会被淹没

那么我们怎么避免在二重循环找`#`的过程中，不会找到重复的`#`。即如何避免一个小岛重复搜索，我们只需要在dfs搜索过程中将我们遍历过的陆地标记为已访问`mark[i][j] = 1`即可。

**总而言之**

*  二重循环，扫描地图中，只要出现`#`，则说明找到一个小岛，则总小岛数+1 `cnt1 ++`，随后以该点进入dfs中深搜
 *  在深搜过程中，将搜索过的点标记已访问，存在不被淹没条件（存在一个`#`满足上下左右都是`#`）的陆地，就说明未被淹没的小岛总数+1 `cnt2 ++`
 *  最后被淹没的小岛数就为`cnt1 - cnt2`

# 解题代码 #

//
    //  main.cpp
    //  2018lanqiao-i
    //
    //  Created by 陈洋 on 2020/10/12.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    #include <iostream>
    #include <queue>
    using namespace std;
    
    typedef pair<int, int> pii;
    queue<pii> q;
    char mmap[1010][1010];
    int mark[1010][1010];
    int n;
    int to[4][2] = {
        {
        0 , 1}, {
        1, 0}, {
        0, -1}, {
        -1, 0}};
    int flag = 0;
    
    void dfs(int x, int y){
        
        for(int i = 0; i < 4; i++){
        
            int nx = x + to[i][0];
            int ny = y + to[i][1];
            
            if(!(nx >= 0 && nx < n && ny >= 0 && ny < n)) continue;
            if(mmap[nx][ny] == '#' && mark[nx][ny] == 0){
        
                mark[nx][ny] = 1;
                if(mmap[nx - 1][ny] == '#' && mmap[nx + 1][ny] == '#' && mmap[nx][ny - 1] == '#' && mmap[nx][ny + 1] == '#')
                    flag = 1;
                dfs(nx,ny);
            }
        }
    }
    
    int main(int argc, const char * argv[]) {
        
        cin >> n;
        
        for(int i = 0; i < n; i++){
        
            for(int j = 0; j < n; j++){
        
                cin >> mmap[i][j];
            }
        }
        
        int cnt1 = 0, cnt2 = 0;
        for(int i = 0; i < n; i++){
        
            for(int j = 0; j < n; j++){
        
                if(mmap[i][j] == '#' && mark[i][j] == 0){
        
                    flag = 0;
                    dfs(i, j);
                    cnt1 ++;
                    if(flag)
                        cnt2 ++;
                }
            }
        }
            
        
        cout << cnt1 - cnt2 << endl;
    }

//测试样例
    
    /*
    7
    .......
    .##....
    .##....
    ....##.
    ..####.
    ...###.
    .......
    
    1
    */
    
    /*
    7
    .....##
    .##...#
    .###...
    ..#.##.
    ..####.
    ...###.
    .......
    
    0
    */
    
    /*
    6
    .###..
    .#.##.
    .####.
    ..###.
    ......
    ......
    
    0
    */
    
    /*
    10
    ..........
    .....#.#..
    .....#....
    .###....#.
    ....###...
    ...#....#.
    ..........
    ..##....#.
    ......##..
    ..........
    
    10
    */