AcWing 843. n-皇后问题
原题链接
中等
作者:
henhen敲
,
2020-06-20 09:36:10
,
所有人可见
,
阅读 706
import java.io.*;
class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int nextInt()throws Exception{
in.nextToken();
return (int)in.nval;
}
static boolean[] r, c, a45, a135;
static char[][] g;
static int n;
public static void DFS(int i, int j, int cnt){
if(i==n&&cnt==0){
for(int x=0; x<n; x++){
for(int y=0; y<n; y++)
out.print(g[x][y]);
out.println("");
}
out.println("");
return;
}
if(i==n) return;
g[i][j] = '.';
DFS((j+1)%n==0?i+1:i, (j+1)%n, cnt);
if(!r[i]&&!c[j]&&!a45[j-i+n]&&!a135[i+j]){
r[i] = true;
c[j] = true;
a45[j-i+n] = true;
a135[j+i] = true;
g[i][j] = 'Q';
DFS((j+1)%n==0?i+1:i, (j+1)%n, cnt-1);
r[i] = false;
c[j] = false;
a45[j-i+n] = false;
a135[j+i] = false;
}
}
public static void main(String[] args)throws Exception{
n = nextInt();
r = new boolean[n];
c = new boolean[n];
a45 = new boolean[2*n];
a135 = new boolean[2*n];
g = new char[n][n];
DFS(0, 0, n);
out.close();
}
}