unomti

用户名：uq_99084910152

访问量：8234

签　名：

等　　级
排　　名	971
经　　验	3396
参赛次数	9
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

买不了ci亏，买的了上当(C语言代码)
浏览：775

题意理解方面的题解
浏览：206

通俗易懂的全排列 c++解法
浏览：987

你可能喜欢

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

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

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

题意理解方面的题解

　　作者: unomti　　　　发表时间：2021-03-30 17:51:53 浏览：206　|　评论：0　

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

</fon
# 一.题意理解
参考该同学的题解https://blog.dotcpp.com/a/72996
但是思路大家可以看看。

题意有两点需要明确
### 1.海岛减少数
题目所描述的是，#块相连即是一个海岛，如果海岛的所有块都消失则该海岛消失。**（一定要反复读题，因为我就理解错了， 想着还有一个海岛分裂为两个海岛的情况）**

明确了这个之后，我们的问题就会转化为，确定该海岛是否**存在**不会沉的块。若存在，则该海岛不会沉。

**（问题解决可用dfs搜索的时候，标记每个海岛是否存在这样的点，最后用总数减去沉岛屿的个数就是减少数。或者每次dfs，用flag标记，如果不存在这样的点就减少数++）**

### 2.边界问题
我之所以说这个问题也是因为我没好好读题，因为**题目中明确地图边界都是海**。但没看见的应该不止我一个。但既然想到了就解决一下。

/*example
		###
		.#.
		...   我们就定义这种情况该岛屿是有一个不会沉的点的 
*/

```cpp
// check 数组返回true代表该点不会沉
bool check(int x, int y) {
	if (x-1>=0 && maps[x-1][y] == '.') return false;
	if (x+1>=0 && maps[x+1][y] == '.') return false;
	if (y-1>=0 && maps[x][y-1] == '.') return false;
	if (y+1>=0 && maps[x][y+1] == '.') return false;
	return true;
}
```
以上check数组即可解决该问题

# 二.题目参考代码

```cpp
#include <iostream>
using namespace std;
int n;
char maps[1005][1005];
int vis[1005][1005];
// 表示每个海岛拥有不会被淹没格子的个数 
int gridPerLand[1000];
int change[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

/*bool check(int x, int y) {
	if (x-1>=0 && maps[x-1][y] == '.') return false;
	if (x+1>=0 && maps[x+1][y] == '.') return false;
	if (y-1>=0 && maps[x][y-1] == '.') return false;
	if (y+1>=0 && maps[x][y+1] == '.') return false;
	return true;
}*/

void dfs(int x, int y, int index) {
	if (x >= n || y >= n || x < 0 || y < 0 || vis[x][y] || maps[x][y] == '.') return;
	vis[x][y] = 1;
	//if(check(x, y)) gridPerLand[index]++; 
	// 题目声明最外边都是海洋，所以无需考虑边界问题直接四面判断是否都是陆地
	if (maps[x-1][y] == '#' && maps[x+1][y] == '#' && maps[x][y+1] == '#' && maps[x][y-1] == '#') gridPerLand[index]++;
	/*example
		###
		.#.
		... 这种情况该岛屿是有一个不会沉的点的 
	*/ 
	for (int i=0; i<4; i++) {
		dfs(x + change[i][0], y + change[i][1], index);
	}
}

int main() {
	scanf("%d", &n);
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			cin >> maps[i][j];
		}
	}
	int island = 0;
	for(int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (vis[i][j] == 0 && maps[i][j] == '#') {
				island++;
				dfs(i, j, island);
			}
		}
	}
	int ans = 0;
	// 如果该海岛没有不会沉的点（即该海岛会沉）则ans++
	for (int i=1; i<=island; i++) {
		if (gridPerLand[i] == 0) ans++; 
	}
	cout << ans << endl;
	return 0;
}
```
好久没写题解了，谢谢大家观看

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

unomti

TA的其他文章

你可能喜欢

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

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

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

不容易系列2 （C语言代码）

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

题意理解方面的题解

评论区

精彩推荐

上车人数（C语言代码）

母牛的故事（C语言代码）

字符串对比（C语言代码）

数组输出（C语言代码）错误？？？

简单的a+b （C语言代码）

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

剪刀石头布（C语言代码）

母牛的故事（C语言代码）

Minesweeper （C语言描述，蓝桥杯）

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

unomti

TA的其他文章

你可能喜欢

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

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

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

不容易系列2 （C语言代码）

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

题意理解方面的题解

评论区

精彩推荐

上车人数 （C语言代码）

母牛的故事 （C语言代码）

字符串对比 （C语言代码）

数组输出 （C语言代码）错误？？？

简单的a+b （C语言代码）

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

剪刀石头布 （C语言代码）

母牛的故事 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

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

　　评论区

上车人数（C语言代码）

母牛的故事（C语言代码）

字符串对比（C语言代码）

数组输出（C语言代码）错误？？？

剪刀石头布（C语言代码）

母牛的故事（C语言代码）