P8662 [蓝桥杯 2018 省 AB] 全球变暖--DFS

题目

解析

这道题的思路就是遍历所有岛屿，判断每一块陆地是否会沉没。对于这种图的遍历，我们首先应该想到DFS。

代码的注意思想就是，在主函数中遍历找出所有岛屿，将其用DFS遍历判断其所有陆地。

注意一下代码中的细节：
【
1.主函数每次给dfs传岛屿时，需要初始化t（记录岛屿是否会沉没）
2.每次用完一个岛屿，将其重新命为其他符号，做标记（DFS核心）
】

讲下DFS

深度优先搜索（DFS）是一种用于遍历或搜索树、图或网格结构的算法，其核心思想是“尽可能深地探索分支，直到尽头再回溯”。

适合使用DFS的场景：
1.连通区域遍历
问题类型：需要找到所有相连的区域（如岛屿、迷宫中的连通路径）。
示例：统计地图中的岛屿数量、标记病毒感染的区域。

2.路径问题
问题类型：寻找从起点到终点的所有可能路径（如迷宫、棋盘游戏）。
示例：判断迷宫是否有出口，计算八皇后问题的解法。

3.状态空间搜索
问题类型：需要穷举所有可能状态的问题（如排列组合、子集生成）。
示例：生成所有可能的括号组合、排列数字。

总结
使用DFS的时机：需要遍历所有可能路径、处理连通区域、或状态空间搜索时。

代码

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n, book[1010][1010], cnt, t, ans, sum;
char map[1010][1010];

int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

void dfs(int x, int y) {
	if (!t) {
		cnt = 0;
		//判断该点【陆地】是否会被淹没用t标记
		for (int i = 0; i < 4; i++) {
			if (map[x + dx[i]][y + dy[i]] != '.')
				cnt++;
			if (cnt == 4) {
				ans += 1;
				t = 1;
			}
		}
	}
	map[x][y] = '*';//标记用过的点
	//开始遍历岛屿上的其他点【陆地】
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
	//越界or不是陆地就跳出
		if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] != '#')
			continue;
		//继续判断该岛屿的其他陆地
		dfs(nx, ny);
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			if (map[i][j] == '#') { //找到岛屿，调用dfs遍历岛屿中的所有陆地
				sum++;
				t = 0;//用于标记该岛屿是否会沉
				dfs(i, j);
			}
		}
	}
	cout << sum - ans << endl;//总岛屿数 - 不会沉没的岛屿数
	return 0;
}