AcWing 843. n-皇后问题
原题链接
中等
作者:
菜鸡就是我
,
2020-07-16 11:33:24
,
所有人可见
,
阅读 573
import java.util.Scanner;
public class Main {
static Scanner in = new Scanner(System.in);
static int[] array;
static int max;
static char[][] arr;
public static void main(String[] args) {
max = in.nextInt();
array = new int [max];
arr = new char[max][max];
Main main = new Main();
main.check(0);
}
public static void check(int n) {
if (n == max) {// n = 8 , 其实8个皇后就已经放好
//先初始化,在转换,在输出
start();
change();
print();
System.out.println();
return;
}
// 依次放入皇后,并判断是否冲突
for (int i = 0; i < max; i++) {
// 先把当前这个皇后 n , 放到该行的第1列
array[n] = i;
// 判断当放置第n个皇后到i列时,是否冲突
if (judge(n)) {// 不冲突
// 接着放n+1个皇后,即开始递归
check(n + 1);
}
// 如果冲突,就继续执行 array[n] = i; 即将第n个皇后,放置在本行得 后移的一个位置
}
}
//重置
public static void start() {
for (int i = 0; i < max; i++) {
for (int j = 0; j < max; j++) {
arr[i][j] = '.';
}
}
}
//一维数组转二维数组
public static void change() {
for (int i = 0; i < max; i++) {
arr[i][array[i]] = 'Q';
}
}
//输出
private static void print() {
for (int i = 0; i < max; i++) {
for (int j = 0; j < max; j++) {
System.out.print(arr[i][j]);
}
System.out.println();
}
}
public static boolean judge(int n) {
for (int i = 0; i < n; i++) {
// 说明
// 1. array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列
// 2. Math.abs(n-i) == Math.abs(array[n] -array[i])表示判断第n个皇后是否和第i皇后是否在同一斜线
// n = 1 放置第 2列 1 n = 1 array[1] = 1
// Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0)= 1
// 3. 判断是否在同一行, 没有必要,n 每次都在递增
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
}