蓝桥杯中的DFS(含算法分析，蓝桥杯真题，解题思路和代码) ...

深度优先搜刮算法 （DFS）     
1.界说：对每一个可能的分支路径深入到不能再转移为止，然后回退到前一步的状态，继续转移到其他状态，云云不停重复，直至找到终极的解。  
深度优先搜刮采用递归函数实现，隐式栈实现。其实我们会发现深度优先搜刮和宽度优先搜刮很像，都是由父节点到子节点的过程，不过每次深度优先搜刮都会优先选择子节点，而直到子节点完全搜刮了，就会回到上一个节点，再到另一个子节点，就相当于原子节点一个兄弟节点，这与宽度优先搜刮优先搜刮兄弟节点相反。而这也为什么说深度优先搜刮是隐式栈，它属于先进后出，根节点是第一个被遍历的，却是最后一个进行搜刮。
如图：遍历顺序

算法分析：

• 必要遍历所有可能性（如分列、组合）。
  
• 路径或连通性问题（如迷宫、图的连通块）。
  
• 递归布局显着的问题（如树、状态转移）。
  
• 共同回溯或剪枝优化暴力搜刮。
  

• 不适合：
  
  
  
  • 最短路径问题（通常用BFS更高效）。
    
  • 大规模数据且深度极深（易栈溢出，需迭代DFS或改用BFS）。
    
  
  

蓝桥杯真题：
环球变暖
题目描述

你有一张某海域 NxNNxN 像素的照片，"."表示海洋、"#"表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于环球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水沉没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被沉没。
例如上图中的海域未来会酿成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你盘算：依照科学家的预测，照片中有多少岛屿会被完全沉没。
输入描述

第一行包含一个整数 N (1≤N≤1000)N (1≤N≤1000)。
以下 NN 行 NN 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 NN 行、第 NN 列的像素都是海洋。、
输出一个整数表示答案。
输入输出样例

示例

   输入

1. 7
2. .......
3. .##....
4. .##....
5. ....##.
6. ..####.
7. ...###.
8. .......

复制代码

   输出

1. 1

复制代码

题目分析：
本题很显着是一个连通性问题，重要要你找连通块的个数，而题目还有一个要求是要预处理输入的数据（一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被沉没。）但是这题真是非常恶心，因为它不是要你求沉没后剩余的岛屿数目，而是要你盘算沉没的岛屿数目，此时你的第一反应就是先用dfs分别算完没有沉没前的岛屿和沉没后的岛屿数，此时你又会发现问题，沉没后的岛屿会分开，也就是可能由一个被分成多个。于是只有两个方向，一个是先找出沉没后会剩余的岛屿数，再盘算本来的岛屿数目，再相减，或者直接找出哪几种岛屿会被沉没，依据它们设计dfs，我个人感觉后者比较麻烦，以是发起采用前者。
代码实现：
  

1. package dfs;
2. import java.util.*;
4. public class Main {
5.     // 定义一个二维数组 arr1 用于表示四个方向：下、上、右、左
6.     static int arr1[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
7.     // 存储原始输入的地图数据
8.     static String arr[][];
9.     // 用于标记地图上的每个位置是否已经被访问过
10.     static boolean visit[][];
11.     // 用于标记当前正在遍历的岛屿是否为不会消失的岛屿
12.     static boolean is;
14.     public static void main(String arg[]) {
15.         // 创建一个 Scanner 对象用于从标准输入读取数据
16.         Scanner sc = new Scanner(System.in);
17.         // 读取地图的边长 n
18.         int n = sc.nextInt();
19.         // 初始化存储原始数据的二维数组
20.         arr = new String[n][n];
21.         // 初始化标记数组，用于记录每个位置是否被访问过
22.         visit = new boolean[n][n];
24.         // 输入地图数据
25.         for (int i = 0; i < n; i++) {
26.             // 将输入的一行字符串按字符分割并存储到数组中
27.             arr[i] = sc.next().split("");
28.         }
30.         // 用于计数不会消失的岛屿数量
31.         int sum = 0;
32.         // 遍历地图上的每个位置
33.         for (int i = 0; i < n; i++) {
34.             for (int j = 0; j < n; j++) {
35.                 // 如果当前位置是陆地 '#' 且未被访问过
36.                 if (arr[i][j].equals("#") && !visit[i][j]) {
37.                     // 初始化标记为 false，表示当前岛屿可能会消失
38.                     is = false;
39.                     // 调用深度优先搜索函数 dfs1 遍历当前岛屿
40.                     dfs1(i, j);
41.                     // 如果当前岛屿不会消失
42.                     if (is) {
43.                         // 不会消失的岛屿数量加 1
44.                         sum++;
45.                     }
46.                 }
47.             }
48.         }
50.         // 用于统计所有的岛屿数量
51.         int sum1 = 0;
52.         // 再次遍历地图上的每个位置
53.         for (int i = 0; i < n; i++) {
54.             for (int j = 0; j < n; j++) {
55.                 // 如果当前位置是陆地 '#'
56.                 if (arr[i][j].equals("#")) {
57.                     // 岛屿数量加 1
58.                     sum1++;
59.                     // 调用深度优先搜索函数 dfs2 遍历当前岛屿并将其标记为已访问
60.                     dfs2(i, j);
61.                 }
62.             }
63.         }
65.         // 输出会消失的岛屿数量，即所有岛屿数量减去不会消失的岛屿数量
66.         System.out.print(sum1 - sum);
67.     }
69.     // 深度优先搜索函数，用于判断当前岛屿是否为不会消失的岛屿
70.     public static void dfs1(int x, int y) {
71.         // 标记当前位置为已访问
72.         visit[x][y] = true;
73.         // 用于标记当前位置是否四周都被陆地 '#' 包围
74.         boolean is1 = true;
75.         // 遍历当前位置的四个相邻位置
76.         for (int t = 0; t < 4; t++) {
77.             // 计算相邻位置的坐标
78.             int x1 = x + arr1[t][0];
79.             int y1 = y + arr1[t][1];
80.             // 如果相邻位置在地图范围内且为水域 '.'
81.             if (x1 >= 0 && x1 < arr.length && y1 >= 0 && y1 < arr.length && arr[x1][y1].equals(".")) {
82.                 // 标记当前位置不是四周都被陆地包围
83.                 is1 = false;
84.             }
85.         }
86.         // 如果当前位置四周都被陆地包围
87.         if (is1) {
88.             // 标记当前岛屿为不会消失的岛屿
89.             is = true;
90.         }
91.         // 再次遍历当前位置的四个相邻位置
92.         for (int t = 0; t < 4; t++) {
93.             // 计算相邻位置的坐标
94.             int x1 = x + arr1[t][0];
95.             int y1 = y + arr1[t][1];
96.             // 如果相邻位置在地图范围内、是陆地 '#' 且未被访问过
97.             if (x1 >= 0 && x1 < arr.length && y1 >= 0 && y1 < arr.length && arr[x1][y1].equals("#") && !visit[x1][y1]) {
98.                 // 标记相邻位置为已访问
99.                 visit[x1][y1] = true;
100.                 // 递归调用 dfs1 函数继续遍历相邻位置
101.                 dfs1(x1, y1);
102.             }
103.         }
104.     }
106.     // 深度优先搜索函数，用于遍历并标记一个岛屿
107.     public static void dfs2(int x, int y) {
108.         // 将当前位置标记为水域 '.'，表示已访问
109.         arr[x][y] = ".";
110.         // 遍历当前位置的四个相邻位置
111.         for (int t = 0; t < 4; t++) {
112.             // 计算相邻位置的坐标
113.             int x1 = x + arr1[t][0];
114.             int y1 = y + arr1[t][1];
115.             // 如果相邻位置在地图范围内且为陆地 '#'
116.             if (x1 >= 0 && x1 < arr.length && y1 >= 0 && y1 < arr.length && arr[x1][y1].equals("#")) {
117.                 // 递归调用 dfs2 函数继续遍历相邻位置
118.                 dfs2(x1, y1);
119.             }
120.         }
121.     }
122. }

复制代码

总结：这类由数组构成的dfs问题，有固定的格式——方向数组（如本题的arr1），记录数组（如本题的visit），然后在差别方向调用处理（如更换visit[x][y]），记取这些格式就差不多可以写出根本的dfs了，bfs也可以这样明白学习。
我的bfs的文章：
蓝桥杯中的BFS(含算法分析，蓝桥杯真题，解题思路和代码)_蓝桥杯不学bfs最佳答案是什么-CSDN博客
题目链接（可以测试一下自己）： 
2.环球变暖 -蓝桥云课

https://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://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://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企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告