（蓝桥杯软件赛Java研究生组/A组）第三章搜索-第一节：DFS和回溯算法

一：DFS基础

（1）概述

DFS（深度优先搜索）：一种用于遍历或搜索树或图的算法。它从起始节点开始，沿着一个路径一直向下探索，直到到达末端节点，然后再回溯并继续探索其他路径。DFS倾向于探索尽可能深的节点，直到达到末端，然后再回溯。DFS通常使用递归来实现，但也可以使用栈来模拟递归的过程

（2）模板

public static void dfs() {if(当前状态 == 目标状态)// 逻辑处理return;for(寻找新状态) {if(状态合法) {dfs(新状态)}}
}

（3）典型题目

题目一：牛客：红与黑

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int ans = 0;public static void dfs(char[][] arr, int i, int j, int m, int n) {ans++;arr[i][j] = '#';// 两个方向的移动量int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};for(int k = 0;k < 4; k++) {int move_x = i + dx[k];int move_y = j + dy[k];if (move_x < 0 || move_x >=m || move_y < 0 || move_y >= n || arr[move_x][move_y] != '.')continue;dfs(arr, move_x, move_y, m, n);}}public static void main(String[] args){Scanner scan = new Scanner(System.in);int m = scan.nextInt();int n = scan.nextInt();int start_i = 0;int start_j = 0;char[][] arr = new char[m][n];for(int i = 0; i < m; i++) {String str = scan.next();char[] str_arr = str.toCharArray();for (int j = 0; j < n; j++) {arr[i][j] = str_arr[j];if (arr[i][j] == '@') {start_i = i;start_j = j;}}}dfs(arr, start_i, start_j, m, n);System.out.println(ans);}
}

二：回溯算法

（1）概述

回溯算法：回溯算法是一种解决问题的算法范式，通常用于解决在搜索问题的解空间时需要考虑多种可能性的情况。这种算法的核心思想是逐步构建解决方案，并在发现当前解决方案不可行时回溯到之前的状态，并尝试其他可能的路径

对于全排列这种问题，用回溯算法解决时，就会生成一颗决策树。遍历整个决策树时，你只需要思考三个问题：

• 路径：你已经做出的选择（当前选择的数字）
• 选择列表：也就是你当前可以做的选择（还能选哪几个数字）
• 结束条件：到达决策树底层，无法再做选择的条件

（2）模板

下面是模板框架

• result：通常设为一个全局变量，用于返回结果
• 选择：做出的一定是合理的选择（根据题意）
• 撤销选择：也就是恢复状态

result = []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(路径, 选择列表)撤销选择

（3）典型题目

题目一：力扣46：全排列

res返回全部排列，record记录一个排列

class Solution {// 返回结果List<List<Integer>> res = new ArrayList<>();// 回溯public void back(int[] nums, List<Integer> record) {// 如果数选择完毕了，那么就增加一个排列if (record.size() == nums.length) {res.add(new ArrayList<>(record));return;}for(int i = 0; i < nums.length; i++) {// 寻找nums[i]在record中是否存在// 如果存在直接下一个if(record.contains(nums[i])){continue;}// 做出选择record.add(nums[i]);back(nums,record);// 撤销选择record.remove(record.size()-1);}}public List<List<Integer>> permute(int[] nums) {// 用于记录已经选择数List<Integer> record = new ArrayList<>();back(nums, record);return res;}
}

题目二：蓝桥云客3824：开心

首先，在 back 方法中，通过递归遍历 arr 数组，依次将每个字符添加到 StringBuilder 对象 str 中。当 str 的长度达到 arr 的长度时，表示已经选择完了所有的字符。此时，如果 k 的值为 0，说明已经选择了 k 个数，可以计算它们的和。这时，我们将 str 转换为字符串，并使用 split("\\+") 方法将其分割成多个子字符串，每个子字符串代表一个数。然后，将每个子字符串转换为长整型并求和，得到结果 res。然后，我们使用 Math.max 和 Math.min 方法更新全局变量 max 和 min，分别记录最大值和最小值。

package environment;import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static long max = Long.MIN_VALUE;static long min = Long.MAX_VALUE;public static void back(int current, char[] arr, int k, StringBuilder str) {if (current == arr.length) {if (k == 0) {String[] s = str.toString().split("\\+");long res = 0;for(String x : s) {res += Long.valueOf(x);}max = Math.max(max, res);min = Math.min(min, res);}return;}str.append(arr[current]);back(current+1, arr, k, str);str.deleteCharAt(str.length()-1);if (k > 0 && current < arr.length-1) {str.append(arr[current]);str.append('+');back(current+1, arr, k-1, str);str.deleteCharAt(str.length()-1);str.deleteCharAt(str.length()-1);}}public static void main(String[] args) throws IOException {Scanner scan = new Scanner(System.in);char[] arr = scan.next().toCharArray();int k = scan.nextInt();StringBuilder str = new StringBuilder();back(0, arr, k, str);System.out.println(max-min);}
}