AcWing 843. n-皇后问题(Java版本)
原题链接
中等
作者:
恒心
,
2021-01-27 00:36:28
,
所有人可见
,
阅读 353
import java.io.*;
import java.util.*;
class Main{
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char[][] g = new char[n][n];
boolean[] col = new boolean[n];
boolean[] dg = new boolean[2*n];
boolean[] udg = new boolean[2*n];
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
g[i][j] = '.';
}
}
dfs(0, n, g, col, dg, udg);
}
public static void dfs(int k, int n, char[][] g, boolean[] col, boolean[] dg, boolean[] udg){
if(k == n){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
System.out.print(g[i][j]);
}
System.out.println();
}
System.out.println();
return;
}
for(int i = 0; i < n; ++i){
if(!col[i] && !dg[n - k + i] && !udg[k + i]){
g[k][i] = 'Q';
col[i] = dg[n - k + i] = udg[k + i] = true;
dfs(k + 1, n, g, col, dg, udg);
col[i] = dg[n - k + i] = udg[k + i] = false;
g[k][i] = '.';
}
}
}
}