蓝桥杯2018年第九届真题-全球变暖-题解（C++代码）

1338 阅读 5 评论 0 点赞

原题链接：蓝桥杯2018年第九届真题-全球变暖

## 思路解析

**准备工作：**

- 首先将图中各字符存入字符型数组`char mp[maxn][maxn]`中。

- 一个访问状态数组`int vis[maxn][maxn]`,0代表未访问，1代表访问过。
- int ans[]：第i个岛屿有多少个符合条件的位置

~~错误思路：一开始没认真读题，被样例误导，然后双重循环遍历数组mp[]，并判断每一个位置上下左右是否有任一方向为‘.’，只要四个方向都不是‘.’就不会被淹没，count++。~~

wa了一遍发现我所求和题目根本不相符，其实存在**一个岛屿**中有多个位置四个方向都是‘#’的。

换句话说，题目所求可以分为两步：
**①在图中有多少多个连通块（岛屿）？
②哪些连通块（岛屿）中存在一个位置四边相邻的都是‘#’.**

**正确思路**：
#### 从数组mp开始遍历，每遍历到一个未被访问过的‘#’，就开始dfs找相连的连通块，并将连通块都设为访问过的状态（使用数组vis[]标记）。
#### 并在边搜索时，判断是否存在位置相邻的四个方向皆为‘#’，若存在则ans[]++，若一个都不存在则ans[]等于0。

最后输出ans[]值为0的个数，即为淹没岛屿的个数。</font>

## AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
char mp[maxn][maxn];
int vis[maxn][maxn];
int ans[100005];
int n;
void dfs(int x, int y, int cnt) {
  if (x<0||y<0||x>=n||y>=n)
    return;
  if (vis[x][y])
    return;
  if (mp[x][y] == '.')
    return;
  vis[x][y] = 1;
  if (mp[x-1][y]=='#'&&mp[x+1][y]=='#'&&mp[x][y-1]=='#'&&mp[x][y+1]=='#')
    ans[cnt]++;
  dfs(x-1,y,cnt);
  dfs(x+1,y,cnt);
  dfs(x,y-1,cnt);
  dfs(x,y+1,cnt);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin>>mp[i][j];
  int len = 0;
  for (int i = 0; i < n; i++) {
    for (int j=0; j<n; j++) {
      if(mp[i][j]=='#'&&!vis[i][j]) {
        dfs(i,j,len);
        len++;
      }
    }
  }
  int sum = 0;
  for (int i = 0; i < len; i++)
    if (ans[i] == 0)
      sum++;
  cout << sum << endl;
}
```

0.0分

7 人评分

本文分类：题解列表
浏览次数：1338 次浏览
发布日期：2020-10-04 17:33:05
本文链接：https://blog.dotcpp.com/a/72996

上一篇 > 蓝桥杯2018年第九届真题-螺旋折线-题解（Java代码）AC代码！
下一篇 > [编程入门]密码破译-题解（C语言代码）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 5 条评论

xr 1年前回复TA

为什么我找你这个写法用java写，只能89，说运行错误：运行时错误，非法的内存访问，数组越界，指针漂移，调用禁用的系统函数。

anan 3年前回复TA

@zjl 三个岛屿被完全淹没。对啊，一共有三个岛屿它们都被淹没了，就是3

zjl 3年前回复TA

怀疑测试用例有问题
如下：
10
..........
..........
...#......
..........
....#.##..
....#.##..
.#..####..
.#........
.##.......
..........
这样的话按题目描述，答案应该是0啊，结果测试结果为3，导致代码AC不了，哪位大神帮解释下

CodeRookie 3年前回复TA

orz

白夜 3年前回复TA

很详细啊

蓝桥杯2018年第九届真题-全球变暖-题解（C++代码）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

评论列表共有 5 条评论

发表评论取消回复