3、DFS &排列数字&n-皇后问题

AcWing 842. 排列数字

AcWing 843. n-皇后问题

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args){
        Main main=new Main();
        main.dfs_pailie();
    }
    int N=10;
    int n;
    boolean flags[]=new boolean[N];
    int path[]=new int[N];
    void dfs(int x){
        //x代表层数
        if(x==n){
            for (int i = 0; i <n; i++) {
                System.out.print(path[i]+" ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            //i没被用过
            if(flags[i]==false){
                path[x]=i;
                flags[i]=true;
                dfs(x+1);
                flags[i]=false;
            }
        }
    }
    void dfs_pailie(){
        Arrays.fill(flags,false);
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        dfs(0);
    }
}

全排列n皇后问题解法

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args){
        Main main=new Main();
        main.dfs_pailie();
    }
    int N=20;
    int n;
    boolean col[]=new boolean[N];
    boolean dg[]=new boolean[N];
    boolean udg[]=new boolean[N];
    char [][]graph=new char[N][N];
    void dfs(int x){
        //x代表层数
        if(x==n){
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    System.out.print(graph[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            //i没被用过
            if(col[i]==false&&dg[x+i]==false&&udg[n-x+i]==false){
                graph[x][i]='Q';
                col[i]=dg[x+i]=udg[n-x+i]=true;
                dfs(x+1);
                col[i]=dg[x+i]=udg[n-x+i]=false;
                graph[x][i]='.';
            }
        }
    }
    void dfs_pailie(){

        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                graph[i][j]='.';
            }
        dfs(0);
    }
}

放与不放两类dfs方法

import java.util.*;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.dfs_pailie();
    }

    int N = 20;
    int n;
    boolean row[] = new boolean[N];
    boolean col[] = new boolean[N];
    boolean dg[] = new boolean[N];
    boolean udg[] = new boolean[N];
    char[][] graph = new char[N][N];

    //ceng是层数
    void dfs(int x, int y, int ceng) {
        //层数超过，直接返回
        if (ceng > n)
            return;
        //一行扫描到头了
        if (y == n) {
            y = 0;
            x++;
        }
        //ceng代表层数
        if (x == n) {
            if (ceng == n) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++)
                        System.out.print(graph[i][j]);
                    System.out.println();
                }
                System.out.println();
            }
            return;
        }
        //不放皇后
        dfs(x, y+1, ceng);

        //放皇后
        //i没被用过
        if (row[x]==false&&col[y] == false && dg[x+y] == false && udg[x-y+n] == false) {
            graph[x][y] = 'Q';
            row[x]=col[y]=dg[x+y]=udg[x-y+n] = true;
            dfs(x+1,0,ceng+1);
            row[x]=col[y]=dg[x+y]=udg[x-y+n] = false;
            graph[x][y] = '.';
        }
    }

    void dfs_pailie() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                graph[i][j] = '.';
            }
        dfs(0,0,0);
    }
}