AcWing 843. n-皇后问题-java
原题链接
中等
作者:
Susu
,
2020-01-26 21:38:28
,
所有人可见
,
阅读 605
import java.util.Scanner;
public class Main {
static int n;
static char[][] g;
static boolean[] col,dg,udg;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
g = new char[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
g[i][j]='.';
}
}
col= new boolean[n];
dg= new boolean[2*n];
udg= new boolean[2*n];
dfs(0);
}
public static void dfs(int u){
if(u==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[i+u] && !udg[i-u+n]) {
g[u][i]='Q';
col[i]=true;dg[i+u]=true;udg[i-u+n]=true;
dfs(u + 1);
col[i]=false;dg[i+u]=false;udg[i-u+n]=false;
g[u][i]='.';
}
}
}
}
import java.util.Scanner;
public class Main {
static int n;
static char[][] g;
static boolean[] row,col,dg,udg;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
g = new char[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
g[i][j]='.';
}
}
row= new boolean[n];
col= new boolean[n];
dg= new boolean[2*n];
udg= new boolean[2*n];
dfs(0,0,0);
}
public static void dfs(int x,int y,int c){
if(y==n){
y=0;x++;
}
if(x==n){
if(c==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;
}
//不放皇后
dfs(x,y+1,c);
//放皇后
if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]) {
g[x][y]='Q';
row[x]=true;col[y]=true;dg[x+y]=true;udg[x-y+n]=true;
dfs(x,y+1,c+1);
row[x]=false;col[y]=false;dg[x+y]=false;udg[x-y+n]=false;
g[x][y]='.';
}
}
}