P8662-蓝桥杯-2018-省-AB-全球变暖-DFS
目录
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;
}