题
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个位置。
。。。
就这样一层一层的递归下去,返回的时候又模拟出不同的情况。