备赛蓝桥----DFS篇

目录

​​排列数字​​

​​n-皇后问题​​

排列数字

import java.util.Scanner;

/**
 * @author yx
 * @date 2022-01-29 14:23
 */
/*
排列数字问题
 */
public class DFS_1 {
    static boolean st[]=new boolean[10];//这两个数组是公用的所以要设置成静态的
    static int path[]=new int[10];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        dfs(0,n);
        return;
    }
    static void dfs(int u,int n){
        if(u==n){//当遍历到最底部时，输出路径上所有的数
            for (int i=0;i<n;i++){
                System.out.print(path[i]);
            }
            System.out.println("");
            return;
        }
        //下面这段代码需要细细去理解
        for (int i=1;i<=n;i++){
            if(!st[i]){//刚开始赋值的时候默认st[i]为false
                path[u]=i;
                st[i]=true;
                dfs(u+1,n);
                st[i]=false;//回溯，恢复原节点
            }
        }
    }
}

n-皇后问题

import java.util.Scanner;

/**
 * @author yx
 * @date 2022-01-29 23:11
 */
/*
八皇后问题
 */
public class DFS_2 {
    static char g[][]=new char[4][4];
    static boolean col[] = new boolean[20];
    static boolean dg[] = new boolean[20];//对角线数组
    static boolean udg[] = new boolean[20];//反对角线数组

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                g[i][j]='.';
            }
        }
        dfs(0,n);
    }
    static void dfs(int u,int n){
        if (u==n){
            for (int i=0;i<n;i++) System.out.println(g[i]);
            System.out.println("");
            return;
        }
        for (int i=0;i<n;i++){
            if (!col[i]&&!dg[u+i]&&!udg[n-u+i]){//下标的原有如图解析所示
                g[u][i]='Q';
                col[i]=dg[u+i]=udg[n-u+i]=true;//表示（u，i）点的列、正斜对角线上被占用
                dfs(u+1,n);//递归
                col[i]=dg[u+i]=udg[n-u+i]=false;//回溯，回复原来的状态
                g[u][i]='.';
            }
        }
    }
}

dg[ u+i]、udg[n-u+i]内下标数字的解析

 总结：

    DFS的核心思想就是递归，上面这两个例子多花时间琢磨琢磨，静下心来感受算法的美。