蓝桥杯中的DFS(含算法分析，蓝桥杯真题，解题思路和代码)
深度优先搜刮算法 （DFS）1.界说：对每一个可能的分支路径深入到不能再转移为止，然后回退到前一步的状态，继续转移到其他状态，云云不停重复，直至找到终极的解。
深度优先搜刮采用递归函数实现，隐式栈实现。其实我们会发现深度优先搜刮和宽度优先搜刮很像，都是由父节点到子节点的过程，不过每次深度优先搜刮都会优先选择子节点，而直到子节点完全搜刮了，就会回到上一个节点，再到另一个子节点，就相当于原子节点一个兄弟节点，这与宽度优先搜刮优先搜刮兄弟节点相反。而这也为什么说深度优先搜刮是隐式栈，它属于先进后出，根节点是第一个被遍历的，却是最后一个进行搜刮。
如图：遍历顺序
https://i-blog.csdnimg.cn/direct/3debbab1c7904065ab8b50d560d51842.png
算法分析：
[*] 必要遍历所有可能性（如分列、组合）。
[*] 路径或连通性问题（如迷宫、图的连通块）。
[*] 递归布局显着的问题（如树、状态转移）。
[*] 共同回溯或剪枝优化暴力搜刮。
[*] 不适合：
[*] 最短路径问题（通常用BFS更高效）。
[*] 大规模数据且深度极深（易栈溢出，需迭代DFS或改用BFS）。
蓝桥杯真题：
环球变暖
题目描述
你有一张某海域 NxNNxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于环球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水沉没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被沉没。
例如上图中的海域未来会酿成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你盘算：依照科学家的预测，照片中有多少岛屿会被完全沉没。
输入描述
第一行包含一个整数 N (1≤N≤1000)N (1≤N≤1000)。
以下 NN 行 NN 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 NN 行、第 NN 列的像素都是海洋。、
输出一个整数表示答案。
输入输出样例
示例
输入
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出
1 题目分析：
本题很显着是一个连通性问题，重要要你找连通块的个数，而题目还有一个要求是要预处理输入的数据（一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被沉没。）但是这题真是非常恶心，因为它不是要你求沉没后剩余的岛屿数目，而是要你盘算沉没的岛屿数目，此时你的第一反应就是先用dfs分别算完没有沉没前的岛屿和沉没后的岛屿数，此时你又会发现问题，沉没后的岛屿会分开，也就是可能由一个被分成多个。于是只有两个方向，一个是先找出沉没后会剩余的岛屿数，再盘算本来的岛屿数目，再相减，或者直接找出哪几种岛屿会被沉没，依据它们设计dfs，我个人感觉后者比较麻烦，以是发起采用前者。
代码实现：
package dfs;
import java.util.*;
public class Main {
// 定义一个二维数组 arr1 用于表示四个方向：下、上、右、左
static int arr1[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// 存储原始输入的地图数据
static String arr[][];
// 用于标记地图上的每个位置是否已经被访问过
static boolean visit[][];
// 用于标记当前正在遍历的岛屿是否为不会消失的岛屿
static boolean is;
public static void main(String arg[]) {
// 创建一个 Scanner 对象用于从标准输入读取数据
Scanner sc = new Scanner(System.in);
// 读取地图的边长 n
int n = sc.nextInt();
// 初始化存储原始数据的二维数组
arr = new String;
// 初始化标记数组，用于记录每个位置是否被访问过
visit = new boolean;
// 输入地图数据
for (int i = 0; i < n; i++) {
// 将输入的一行字符串按字符分割并存储到数组中
arr = sc.next().split("");
}
// 用于计数不会消失的岛屿数量
int sum = 0;
// 遍历地图上的每个位置
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 如果当前位置是陆地 '#' 且未被访问过
if (arr.equals("#") && !visit) {
// 初始化标记为 false，表示当前岛屿可能会消失
is = false;
// 调用深度优先搜索函数 dfs1 遍历当前岛屿
dfs1(i, j);
// 如果当前岛屿不会消失
if (is) {
// 不会消失的岛屿数量加 1
sum++;
}
}
}
}
// 用于统计所有的岛屿数量
int sum1 = 0;
// 再次遍历地图上的每个位置
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 如果当前位置是陆地 '#'
if (arr.equals("#")) {
// 岛屿数量加 1
sum1++;
// 调用深度优先搜索函数 dfs2 遍历当前岛屿并将其标记为已访问
dfs2(i, j);
}
}
}
// 输出会消失的岛屿数量，即所有岛屿数量减去不会消失的岛屿数量
System.out.print(sum1 - sum);
}
// 深度优先搜索函数，用于判断当前岛屿是否为不会消失的岛屿
public static void dfs1(int x, int y) {
// 标记当前位置为已访问
visit = true;
// 用于标记当前位置是否四周都被陆地 '#' 包围
boolean is1 = true;
// 遍历当前位置的四个相邻位置
for (int t = 0; t < 4; t++) {
// 计算相邻位置的坐标
int x1 = x + arr1;
int y1 = y + arr1;
// 如果相邻位置在地图范围内且为水域 '.'
if (x1 >= 0 && x1 < arr.length && y1 >= 0 && y1 < arr.length && arr.equals(".")) {
// 标记当前位置不是四周都被陆地包围
is1 = false;
}
}
// 如果当前位置四周都被陆地包围
if (is1) {
// 标记当前岛屿为不会消失的岛屿
is = true;
}
// 再次遍历当前位置的四个相邻位置
for (int t = 0; t < 4; t++) {
// 计算相邻位置的坐标
int x1 = x + arr1;
int y1 = y + arr1;
// 如果相邻位置在地图范围内、是陆地 '#' 且未被访问过
if (x1 >= 0 && x1 < arr.length && y1 >= 0 && y1 < arr.length && arr.equals("#") && !visit) {
// 标记相邻位置为已访问
visit = true;
// 递归调用 dfs1 函数继续遍历相邻位置
dfs1(x1, y1);
}
}
}
// 深度优先搜索函数，用于遍历并标记一个岛屿
public static void dfs2(int x, int y) {
// 将当前位置标记为水域 '.'，表示已访问
arr = ".";
// 遍历当前位置的四个相邻位置
for (int t = 0; t < 4; t++) {
// 计算相邻位置的坐标
int x1 = x + arr1;
int y1 = y + arr1;
// 如果相邻位置在地图范围内且为陆地 '#'
if (x1 >= 0 && x1 < arr.length && y1 >= 0 && y1 < arr.length && arr.equals("#")) {
// 递归调用 dfs2 函数继续遍历相邻位置
dfs2(x1, y1);
}
}
}
}总结：这类由数组构成的dfs问题，有固定的格式——方向数组（如本题的arr1），记录数组（如本题的visit），然后在差别方向调用处理（如更换visit），记取这些格式就差不多可以写出根本的dfs了，bfs也可以这样明白学习。
我的bfs的文章：
蓝桥杯中的BFS(含算法分析，蓝桥杯真题，解题思路和代码)_蓝桥杯不学bfs最佳答案是什么-CSDN博客
题目链接（可以测试一下自己）：
2.环球变暖 -蓝桥云课https://csdnimg.cn/release/blog_editor_html/release2.3.8/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=P1C7https://www.lanqiao.cn/problems/178/learning/?page=1&first_category_id=1&second_category_id=3&tags=%E7%9C%81%E8%B5%9B,DFS&tag_relation=intersection
还有几道蓝桥杯的dfs可以练手：
1.正则问题 - 蓝桥云课https://csdnimg.cn/release/blog_editor_html/release2.3.8/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=P1C7https://www.lanqiao.cn/problems/106/learning/?page=1&first_category_id=1&second_category_id=3&tags=%E7%9C%81%E8%B5%9B,DFS&tag_relation=intersection3.小朋友崇敬圈 - 蓝桥云课https://csdnimg.cn/release/blog_editor_html/release2.3.8/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=P1C7https://www.lanqiao.cn/problems/182/learning/?page=1&first_category_id=1&second_category_id=3&tags=%E7%9C%81%E8%B5%9B,DFS&tag_relation=intersection
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]