（蓝桥杯软件赛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(路径)
        return

    for 选择 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);
	
    }
}