特辣的海藻！8

题

1.843. n-皇后问题 - AcWing题库

 大名鼎鼎N皇后

import java.util.*;

public class Main {
    static int N = 10;
    static int n;
    static char[][] map = new char[N][N];
    static boolean[] row = new boolean[N];
    static boolean[] col = new boolean[N];
    static boolean[] dg = new boolean[N*2];
    static boolean[] udg = new boolean[N*2];

    static void dfs(int u, int x, int y) {
        if(u > n)
            return ;
        if(y == n) {
            y = 0;
            x += 1;
        }

        if(x == n) {
            if(u == n) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        System.out.print(map[i][j]);
                    }
                    System.out.println();
                }
                System.out.println();
            }
            return ;
        }

        // 这一列不放皇后
        dfs(u, x, y+1);

        if(!row[x] && !col[y] && !dg[x-y+n] && !udg[x+y]) {
            map[x][y] = 'Q';
            row[x] = col[y] = dg[x-y+n] = udg[x+y] = true;
            dfs(u+1, x, y+1);
            map[x][y] = '.';
            row[x] = col[y] = dg[x-y+n] = udg[x+y] = false;
        }

    }


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++) {
                map[i][j] = '.';
            }
        }

        dfs(0, 0, 0);

        scan.close();
    }

}

//zhuanxinyidian!!!

这是第一种搜索顺序，目前先掌握这一种。

N皇后的思路就是，按照行的顺序，以每一行的视角来看每一列，这样来遍历每一个格子是不是能放皇后，u记录当前放的是第几个皇后。

当u>n的时候，说明已经遍历到最底层，我们可以开始模拟放皇后，一层一层返回了。当y==n时，说明此时遍历的位置已经超出边界，换下一行的第一个格子看。当x==n时u==n，说明在最后一行，最后一个皇后也放好了，说明当前这个矩阵就满足条件了，可以输出了。

因为是深度优先遍历，是一定会一行一行的遍历下去的。然后对于每一行来说，有两种选择，第一是在这一列放皇后，判断位置是否满足条件；第二是向下一层递归，在下一列放皇后。

如果这一行、这一列、主对角线、副对角线都没有放过皇后，那么久放！然后将标记数组给标记一下。放的皇后个数加1，列加1，为什么不行加1，因为我们要模拟所有的格子，模拟每种情况，不能漏掉。

2.842. 排列数字 - AcWing题库

import java.util.*;

public class Main {
    static int n;
    static final int N = 10;
    static int[] path = new int[N];
    static boolean[] st = new boolean[N];
    
    static void dfs(int u) {
        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] = true;
                path[u] = i;
                
                dfs(u+1);
                
                // 不恢复也可以，因为后续这个path[i]会不断被覆盖
                path[u] = 0;
                st[i] = false;
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        
        dfs(0);    
        
        scan.close();
    }
}

有n个位置放数字，第一个位置的数字放好之后，还有n-1个位置。

对于第n-1个位置，第n-1个位置放好之后，还有n-2个位置。

。。。

就这样一层一层的递归下去，返回的时候又模拟出不同的情况。