acwing DFS BFS学习笔记
DFS（回溯+剪枝）
DFS注意顺序
一条路走到黑即选择一个方法一直走到尾部，到尾部之后返回上一个节点判断另一个方案直到本节点可以访问的节点区别访问完毕
桉树型结构来理解的话类似前序遍历
树的前序遍历是指对于树中的每个节点，先访问该节点，然后递归地访问该节点的左子树，再递归地访问该节点的右子树。树的中序遍历是指对于树中的每个节点，先递归地访问该节点的左子树，再访问该节点，最后递归地访问该节点的右子树。树的后序遍历是指对于树中的每个节点，先递归地访问该节点的左子树，再递归地访问该节点的右子树，最后访问该节点。简单来说，前序遍历是根左右，中序遍历是左根右，后序遍历是左右根。这三种遍历的顺序不同，因此它们可以被用来完成不同的任务。例如，在二叉搜索树中，中序遍历可以按照顺序访问树中的所有节点，因此可以用来排序。后序遍历则可以用来计算树中节点的后继和前驱。
经典案例：
给定一个整数 nn，将数字 1∼n1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 nn。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤71≤n≤7
输入样例：
3
输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
package ACWing.SearchAndGraphTheory.DFS;
//842. 排列数字
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/15 18:42
*/
public class StaggeredNumerals {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
ArrayList<Integer> list=new ArrayList<>();
boolean[]arr=new boolean[n+1];
dfs(list,n,arr);
}
public static void dfs(ArrayList<Integer> list,int n,boolean[]arr){
if(list.size()==n){
for (Integer integer : list) {
System.out.print(integer+" ");
}System.out.println();
return;
}
for (int i = 1; i <= n; i++) {
if (!arr[i]){
list.add(i);
arr[i]=true;
dfs(list,n,arr);
//恢复现场回归到上次的状态
list.remove(list.size()-1);
arr[i]=false;
}
}
}
}
经典8皇后问题
package ACWing.SearchAndGraphTheory.DFS;
//843. n-皇后问题
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/15 22:13
*/
public class NQueensRroblem {
static String[][]arr=new String[20][20];//用截距来判断b=y+x所以有可能是20所以用20
static boolean[]col=new boolean[20];
static boolean[]dg=new boolean[20];
static boolean[]udg=new boolean[20];
static boolean[]row=new boolean[20];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
arr[i][j]=".";
}
}
//dfs(0,n);
dfs2(0,0,0,n);
}
public static void dfs(int u,int n){
if(u==n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
for (int i = 0; i < n; i++) {
if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){//精华所在用截距来判断对角线
arr[u][i]="Q";
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1,n);
col[i]=dg[u+i]=udg[n-u+i]=false;
arr[u][i]=".";
}
}
}
//解法二与上解法的差别在于解法二通过递归遍历了整个节点去判断是否要放皇后解法一是通过循环去判断一整行如何递归到下一行
public static void dfs2(int x,int y,int s,int n){
//设置边界条件
if(y==n){
y=0;
x++;
}
if(x==n){
if(s==n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
System.out.println();
}return;
}
//不放皇后
dfs2(x,y+1,s,n);
//放皇后
if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){//条件允许的情况下放皇后
arr[x][y]="Q";
row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
dfs2(x,y+1,s+1,n);
row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;
arr[x][y]=".";
}
}
}
大体的思路一致没有具体的模板
弹出（边界）条件
进入符合条件的递归
恢复现场
刷题总结：
先判断暴力搜索的情况是否为有顺序的接下去搜索还是全排列，因为时间复杂度不够确定所以尽可能剪枝来缩小查询次数
如果是不按顺序搜索的话一般情况下便是这种模板（全排列）
例题：//184. 虫食算 InsectFeedingCalculation
private static boolean dfs(int u) {
if(u==n){
return true;
}
for (int i = 0; i < n; i++) {
if(!st[i]){
path[qu[u]]=i;
st[i]=true;
if(check()&&dfs(u+1)){
return true;
}
path[qu[u]]=-1;
st[i]=false;
}
}
return false;
}
如果是按顺序搜索的话一般便是这种模板（内含有一个遍历的过程必须按照顺序进行遍历组合）即按顺序进行选择来遍历所有的选择情况每种情况之后都必须要恢复现场
例题//187. 导弹防御系统 MissileDefenseSystem
public static void dfs(int[]arr,int su,int sd,int k,int n){
弹出条件
第一种一种情况
第二种情况
.
.
.
}
dfs求组合数类型：
先对要组合的数排序再进行dfs而且必须保证值的不降序性
洛谷例题：
package luogu.dfs;
//P1036 [NOIP2002 普及组] 选数
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/22 21:38
*/
public class Selectron {
static boolean[]st=new boolean[30];
static int n;
static int m;
static int sum=0;
static List<Integer> set=new ArrayList<>();
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
int[]arr=new int[n];
for (int i = 0; i < n; i++) {
arr[i]=sc.nextInt();
}
Arrays.sort(arr);
dfs(0,0,arr);
int num=0;
for (Integer integer : set) {
if(sushu(integer)){
num++;
}
}
System.out.println(num);
}
public static void dfs(int u,int a,int[]arr){//a和u其实可以合并
if(u==m){
set.add(sum);
return;
}
for (int i = a; i < n; i++) {
if(!st[i]){
sum=sum+arr[i];
st[i]=true;
dfs(u+1,i+1,arr);
sum=sum-arr[i];
st[i]=false;
}
}
}
public static boolean sushu(int a){
for (int i = 2; i < Math.sqrt(a); i++) {
if(a%i==0){
return false;
}
}
return true;
}
}
BFS
按数来理解的话就是依次遍历整层，一层一层遍历，适用与查找最短路径，最短步数等等根据情况使用
将所有一步可以走到的节点全部存到队列中，因为队列的先进先出特性所以必定可以保证先遍历完路径为1的节点才能去遍历2的节点所以保证了到某个点的距离最短
经典迷宫问题
给定一个 n×mn×m 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)(n,m) 处，至少需要移动多少次。
数据保证 (1,1)(1,1) 处和 (n,m)(n,m) 处的数字为 00，且一定至少存在一条通路。
输入格式
第一行包含两个整数 nn 和 mm。
接下来 nn 行，每行包含 mm 个整数（00 或 11），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤1001≤n,m≤100
输入样例：
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出样例：
8
思路将这一层符合条件的坐标放入队列中，在进入下一层时从队列中取出上一层的坐标进行上下左右的判断以此类推最后遍历到最后一层无法遍历为止
便可以求出这个点到每个点的最短路径（权重相等时是最短路径）
package ACWing.SearchAndGraphTheory.BFS;
//844 走迷宫
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
/**
* @author :chenjie
* @date :Created 2022/12/15 18:42
*/
public class WalkTGHEMaze {
static class Pall{
int x;
int y;
public Pall(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "Pall{" +
"x=" + x +
", y=" + y +
'}';
}
}
static Pall[][]palls=new Pall[110][110];//记录路径
static Queue<Pall> queue=new ArrayDeque<>();
static int[][]d=new int[110][110];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int[][]arr=new int[n][m];
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < m; j++) {
arr[i][j]=sc.nextInt();
}
}
//初始化距离-1为未被访问过
for (int i = 0; i <n; i++) {
for (int j = 0; j < m; j++) {
d[i][j]=-1;
}
}
System.out.println(bfs(n, m, arr));
int x=n-1,y=m-1;
while (x!=0||y!=0){
System.out.println(x+" "+y);
x=palls[x][y].x;
y=palls[x][y].y;
}
}
public static int bfs(int n,int m,int[][]arr){
queue.add(new Pall(0,0));
palls[0][0]=new Pall(0,0);
d[0][0]=0;
//扩展元素的坐标上下左右
int[]dx={-1,0,1,0};
int[]dy={0,1,0,-1};
while (queue.size()>0){
Pall t=queue.poll();
for (int i = 0; i < 4; i++) {
int x=t.x+dx[i],y=t.y+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&d[x][y]==-1&&arr[x][y]==0){
d[x][y]=d[t.x][t.y]+1;
palls[x][y]=t;
queue.add(new Pall(x,y));
}
}
}
return d[n-1][m-1];
}
}
package ACWing.SearchAndGraphTheory.BFS;
//845. 八数码
import java.util.*;
/**
* @author :chenjie
* @date :Created 2022/12/17 13:01
*/
/**
* 本题的总体思路：
* bfs：将所有一步可以走到的节点全部存到队列中，因为队列的先进先出特性所以必定可以保证先遍历完路径为1的节点才能去遍历2的节点所以保证了到某个点的距离最短
* 而本题难点在于如何存储节点的状态和存储节点对应的距离
* 存储节点的状态：题目也有提示1 2 3 x 4 6 7 5 8这样输入便是可以将二维数组压成一维。在进行做题
* 存储节点对应的距离：刚好就对应hashmap类
*/
public class TheEightDigits {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s="";
for (int i = 0; i < 9; i++) {
s+=sc.next();
}
System.out.println(s);
System.out.println(bfs(s));
}
public static int bfs(String t){
Queue<String> queue=new ArrayDeque<>();//记录状态
queue.add(t);
Map<String ,Integer> map=new HashMap<>();//记录对应的步数
map.put(t,0);
int[]dx={1,-1,0,0};
int[]dy={0,0,1,-1};
while (!queue.isEmpty()){
String s = queue.remove();
if("12345678x".equals(s)){
return map.get(s);
}
int n=s.indexOf('x');
int x=n/3;
int y=n%3;
for (int i = 0; i < 4; i++) {
int a=x+dx[i],b=y+dy[i];//遍历上下左右
if(a>=0&&b>=0&&a<3&&b<3){
int l=map.get(s);
String str=swap(s,n,a*3+b);//必须用对象来接副本不然直接用s=的话会出现意外
if(map.containsKey(str)){//如果已经走过来便不在走
continue;
}
map.put(str,l+1);
queue.add(str);
}
}
}
return -1;
}
/**
* setCharAt是精髓所在原本我只能转成char在操作现在可以在字符串上进行修改
* 交换字符串中的俩个字符
* @param s 字符串11
* @param x x的位置下标
* @param x2 交换位的位置下标
* @return
*/
public static String swap(String s,int x,int x2){
StringBuilder str=new StringBuilder(s);
str.setCharAt(x,s.charAt(x2));
str.setCharAt(x2,'x');
return str.toString();
}
}
俩者区别：
