DFS概要：
要想学会深度优先搜索的题目，首先需要知道他的代码原理，适用场景
基本原理：
DFS是基于遍历，搜索树，图的算法，通过从根节点（或任意起始节点）开始，沿着每个分支深入访问节点，直到到达叶子节点或没有未访问的邻居节点为止，然后回溯到上一个节点，继续搜索其他未访问的分支。
特点：
1、深度优先：DFS 按照深入的方式搜索，每次递归或扩展时尽量向树的“深度”方向探索，直到到达树的末端或遇到没有未访问邻居的节点为止。
2、回溯：当某个分支的所有节点都被访问过，DFS 会回溯到上一个分支节点，继续从这个节点开始搜索其他未被访问的分支。
适用场景：
1、解空间为树或图的遍历问题
- 在一个无向图中寻找连通分量。
- 在树中搜索某个节点或路径。
- 在图中检查图的连接性。
- 求解图的最短路径问题（例如，基于 DFS 的拓扑排序或割点检测）。
2. 问题的解空间较大，但解决方案可以通过回溯探索所有可能的路径
- 当问题的解空间非常大，但解决方案需要从一个状态递归地推进并逐步寻找可能的解时，DFS 非常有效。经典应用包括：
- 排列与组合问题：生成所有可能的排列或组合。例如，数字
1到n的全排列。 - 子集问题：例如，给定一个集合，找出它的所有子集。
- 背包问题：DFS 可以用于暴力破解的背包问题，尤其在没有明确动态规划解法时。
- 迷宫问题：在一个迷宫中找到从起点到终点的路径。
- 排列与组合问题：生成所有可能的排列或组合。例如，数字
3. 当递归的状态空间较小且回溯合适时
-
DFS 适合用于那些需要从当前状态探索所有子状态的场景。通过递归或者显式的栈来维护当前的状态，并返回到上一个状态继续探索。例如：
- 回溯算法：通过递归尝试每种可能的选择，并在不能继续时“回溯”并撤销之前的选择，尝试其他可能。
- 数独问题：可以使用 DFS 和回溯来尝试填充数独的每个空格。
4. 寻找最优解或满足条件的解
- DFS 不仅用于遍历，还可以用来找到满足特定条件的解。例如：
- 求解最短路径（不一定是最优）：DFS 可以用来寻找图中从一个节点到另一个节点的路径。
- 判断某个条件是否成立：例如，在图中寻找是否存在一个满足特定约束的路径。
5. 当解空间是深度优先的方式来探索
- 如果你希望通过逐步深入某一条路径直到无法继续，再返回并探索其他路径，这种场景特别适合使用 DFS。
- 深度优先的探索问题：如图形或树形结构的搜索。
- 实现递归结构的问题：例如解析递归定义的问题，如树形递归结构或递归数据结构的操作。
6. 问题空间可以通过剪枝避免冗余计算
- 在很多问题中，可以通过剪枝技术，减少不必要的探索，从而提高 DFS 的效率。例如：
- 在深度优先搜索过程中，遇到重复的状态或不符合条件的路径时，可以立即停止继续搜索。
7. 空间限制不严苛的情况下使用
- 虽然 DFS 使用栈来存储状态，但它的空间复杂度通常是线性的，即
O(n)，对于深度较大的问题或没有显著的空间限制时，DFS 是一种理想的选择。如果问题的规模过大，栈可能会溢出，因此在有较高空间要求的情况下，可能需要改为广度优先搜索（BFS）或动态规划来优化空间使用。
2024/12/2 DAY1、
题目网址：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in );
int n = sc.nextInt();
boolean[] visits = new boolean[n];
//初始化数组，true表示遍历过这个数，false表示没有遍历过这个数。
Arrays.fill(visits,false);
//current表示当前的要输出的数组
List<Integer> current = new ArrayList<>();
dfs(n,visits,current);
}
private static void dfs(int n, boolean[] visits, List<Integer> current) {
if(current.size() == n){
for (Integer num : current) {
System.out.printf("%5d",num );
}
System.out.println();
return;
}
for (int i = 1; i <= n; i++) {
if(!visits[i - 1 ]){
visits[i - 1] = true;
current.add(i);
dfs(n,visits,current);
//2、回溯
current.remove(current.size() - 1);
visits[i - 1] = false;
}
}
}
}
全排列问题：
考虑使用dfs深度优先搜索算法
维护一个当前遍历过的数组打印数据的时候使用，和一个visit数组用来记录该数是否用过。
记录遍历过得数据，当他长度等于输入得n得时候打印出数组
细节：
因为要求按照字典顺序排列，而内部dfs回溯使用1-9得循环，必然使从小到大，满足其条件。
要求有5个场宽，可以使用
printf("%5d",num);
2024/12/3 DAY2、
题目网址：
有复杂的空间约束条件：
考虑使用回溯算法
package LanQiao.M.Dec3;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static int count = 0;
private static int num = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in );
int n = sc.nextInt();
boolean[][] visit = new boolean[n][n];
//默认为false
List<Integer> list = new ArrayList<>(n);
dfs(visit,n,0,list);
System.out.println(count);
}
private static void dfs(boolean[][] visit, int n, int row, List<Integer> list) {
if (row == n ) {
for (Integer integer : list) {
if(num < 3){
System.out.print(integer + 1 + " ");
}
}
if(num < 3){
System.out.println();
}
num++;
count++;
return;
}
// 在当前行尝试放置棋子
for (int col = 0; col < n; col++) {
if (condition(list, row, col)) {
visit[row][col] = true; // 放置棋子
list.add(col);
dfs(visit, n, row + 1, list); // 递归到下一行
list.remove(list.size() - 1);
visit[row][col] = false;
}
}
}
private static boolean condition(List<Integer> list, int row, int col) {
for (int i = 0; i < row; i++) {
// 检查列是否已经有棋子，检查对角线是否冲突
int queenPosition = list.get(i);
if (queenPosition == col || Math.abs(queenPosition - col) == row - i) {
return false;
}
}
return true;
}
}
2024/12/4 DAY3、
题目网址：
迷宫问题，同样是简单的回溯算法
参考代码
package LanQiao.M.Dec4;
import java.util.Scanner;
public class Main {
public static int count = 0;
//上，右，下，左
public static int[][] Way = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in );
int N,M,T;
N = sc.nextInt();
M = sc.nextInt();
T = sc.nextInt();
int[] Start = new int[2];
int[] Final = new int[2];
boolean[][] isGone = new boolean[N][M];
for (int i = 0; i < 2; i++) {
Start[i] = sc.nextInt() - 1;
}
for (int i = 0; i < 2; i++) {
Final[i] = sc.nextInt() - 1;
}
for (int i = 0; i < T ; i++) {
isGone[sc.nextInt() - 1][sc.nextInt() - 1] = true;
}
dfs(Start,Final,isGone);
System.out.println(count);
}
private static void dfs( int[] start, int[] Final,boolean[][] isGone) {
if(start[0] == Final[0] && start[1] == Final[1]){
count++;
return;
}
for (int i = 0; i < 4; i++) {
int newRow = start[0] + Way[i][0];
int newCol = start[1] + Way[i][1];
if(GO(newRow,newCol,isGone)){
isGone[newRow][newCol] = true;
dfs(new int[] {newRow, newCol}, Final, isGone); // 使用新的坐标数组
isGone[newRow][newCol] = false;
}
}
}
private static boolean GO(int newRow, int newCol, boolean[][] isGone){
return newRow >= 0 && newRow < isGone.length &&
newCol >= 0 && newCol < isGone[0].length &&
!isGone[newRow][newCol];
//该位置是否为ture;
}
}
2024/12/5 DAY4、
题目网址：
优化思路：
再DFS的基础上增加了记忆化搜索。
增加一个数组用来记录走到当前楼层的最小次数，如果后面的次数比这个树大，就执行剪枝操作。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 楼层数
int A = sc.nextInt(); // 起始楼层
int B = sc.nextInt(); // 目标楼层
int[] K = new int[N]; // 每层的按键信息
for (int i = 0; i < N; i++) {
K[i] = sc.nextInt();
}
//索引要减去1
int result = dfs(N, A - 1, B - 1, K, new Integer[N], 0);
System.out.println(result);
}
public static int dfs(int N, int current, int target, int[] K, Integer[] memo, int presses) {
if (current == target) {
return presses;
}
// 如果已经访问过该楼层并且按键次数较小，直接返回
if (memo[current] != null && memo[current] <= presses) {
return -1;
}
// 更新记忆化表
memo[current] = presses;
// 上升到目标楼层
int minPresses = Integer.MAX_VALUE;
// 计算上升和下降的目标楼层
int up = current + K[current];
int down = current - K[current];
// 处理上升的楼层
if (up >= 0 && up < N) {
int result = dfs(N, up, target, K, memo, presses + 1);
if (result != -1) {
minPresses = Math.min(minPresses, result);
}
}
// 处理下降的楼层
if (down >= 0 && down < N) {
int result = dfs(N, down, target, K, memo, presses + 1);
if (result != -1) {
minPresses = Math.min(minPresses, result);
}
}
// 返回最小的按键次数
return minPresses == Integer.MAX_VALUE ? -1 : minPresses;
}
}
2024/12/6 DAY5、
题目网址： https://www.lanqiao.cn/problems/89/learning/?page=1&first_category_id=1&tag_relation=intersection
package LanQiao.M.Dec6;
import java.util.Scanner;
public class Main {
static int[] path;
static int n;
static int[] cntx;
static int[] cnty;
static boolean[][] visited;
private static boolean success;
static int dx[] = {1, 0, -1, 0};//控制走的方向
static int dy[] = {0, 1, 0, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();//n*n格子
cntx = new int[n];
cnty = new int[n];
path = new int[n * n];
visited = new boolean[n][n];
sc.nextLine();
for (int i = 0; i < n; i++) {
cntx[i] = sc.nextInt();
// tot += cntx[i];
}
for (int i = 0; i < n; i++) {
cnty[i] = sc.nextInt();
// tot += cnty[i];
}
dfs(0, 0, 0);
}
private static void dfs(int x, int y, int step) {
path[step] = y * n + x; //将该点编号记录到路径中
visited[x][y] = true;//将该点标记为已经走过的状态
cntx[x]--;//拔掉对应的箭
cnty[y]--;
if (x == n - 1 && y == n - 1 && check())
{
success = true;
for (int i = 0; i <= step; i++)//输出答案。
{
System.out.print(path[i]+" ");
}
return;
}
for (int i = 0; i < 4; i++)//上下左右四个方向搜索下一步
{
int xx = x + dx[i], yy = y + dy[i];
if (!success && 0 <= xx && xx <= n-1 && yy >= 0 && yy <= n-1&& !visited[xx][yy] )//没有到达终点，下一步(xx,yy)未走过且在地图范围内
{
if (cntx[xx] > 0 && cnty[yy] > 0)//该点对应箭靶上有箭，说明该点可以走
{
dfs(xx, yy, step + 1);//搜索下一步
visited[xx][yy] = false;//复原，回溯
cntx[xx]++;
cnty[yy]++;
}
}
}
}
private static boolean check() {
for (int i = 0; i < n; ++i) {
if (cntx[i] != 0 || cnty[i] != 0)
return false;
}
return true;
}
}