枉夙

用户名：uq_22131682797

访问量：1429

签　名：

等　　级
排　　名	28992
经　　验	477
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

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

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

优质题解

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

　　作者: 枉夙　　　　发表时间：2020-10-04 17:33:05 浏览：1176　|　评论：4　

原题链接：蓝桥杯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分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

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

2023-03-07 21:08:32

zjl

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

2021-04-16 17:41:55

CodeRookie

orz

2021-03-14 18:30:19

白夜

很详细啊

2021-01-21 14:51:26

枉夙

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

Biggest Number (错误代码时间超限制)

聪明的美食家（C语言代码）

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

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

评论区

精彩推荐

最长单词（C语言代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

Wu-求圆的面积（C++代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

A+B for Input-Output Practice (V) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

买不到的数目（C语言代码）

枉夙

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

Biggest Number (错误代码时间超限制)

聪明的美食家 （C语言代码）

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

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

评论区

精彩推荐

最长单词 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

Wu-求圆的面积 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

A+B for Input-Output Practice (V) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

良心推荐——>题解1049：C语言程序设计教程（第三版）课后习题11.1 （C语言描述——简单明了，时间复杂度低）

买不到的数目 （C语言代码）

聪明的美食家（C语言代码）

上车人数（C语言代码）

　　评论区

最长单词（C语言代码）

用筛法求之N内的素数。（C语言代码）

Wu-求圆的面积（C++代码）

买不到的数目（C语言代码）