AcWing 843. n-皇后问题_java实现含注释_2种方式
原题链接
中等
作者:
FayunYm
,
2021-01-01 15:29:43
,
所有人可见
,
阅读 342
import java.util.Scanner;
public class Main {
static final int N = 20; //对角线需要20才能放下
static int n;
static char[][] checkBoard = new char[N][N];//棋盘
static boolean[] col = new boolean[N]; //列
static boolean[] dg = new boolean[N]; //对角线,左上角为第一条
static boolean[] udg = new boolean[N]; //反对角线。右上角为第二条
static boolean[] row = new boolean[N]; //dfs2方法需要
static void dfs1(int u) {
if(u == n) {
//不能用这个for,不然会遍历N次
// for(char[] row : checkBoard) {
// System.out.println(row);
// }
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
System.out.print(checkBoard[i][j]);
}
// System.out.println(checkBoard[i]); IDEA上直接这样既可,不知道这里是什么原因
System.out.println();
}
System.out.println();
return;
}
for(int i = 0; i < n; i++) {
if(!col[i] && !dg[u+i] && !udg[n-u+i]) { //确保皇后所在列、对角线、反对角线无其他皇后
col[i] = dg[u+i] = udg[n-u+i] = true;
checkBoard[u][i] = 'Q';
dfs1(u+1);
//恢复现场
col[i] = dg[u+i] = udg[n-u+i] = false;
checkBoard[u][i] = '.';
}
}
}
static void dfs2(int x, int y, int s) {
if (y == n) { //y越界,说明应该是下一行了
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(checkBoard[i][j]);
}
System.out.println();
}
System.out.println();
}
return; //x == n时,无论s是否==0,都要退出
}
//选择不放皇后
dfs2(x,y+1,s);
//选择放皇后
if(!col[y] && !dg[x+y] && !udg[n-y+x] && !row[x]) {
checkBoard[x][y] = 'Q';
col[y] = dg[x+y] = udg[n-y+x] = row[x] = true;
dfs2(x,y+1,s+1);
col[y] = dg[x+y] = udg[n-y+x] = row[x] = false;
checkBoard[x][y] = '.';
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
checkBoard[i][j] = '.';
}
}
dfs2(0,0,0); //第0行开始
}
}