问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
package base27; import java.util.Scanner; public class Main { static int count = 0; static int n; static int[] w_place; static int[] b_place; static int[][] a; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); a = new int[n][n]; w_place = new int[n]; b_place = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = in.nextInt(); } } backTrace(0); //双回溯 System.out.println(count); } private static void backTrace(int i) {//m为从上到下递增的行数 w为左到右的列 if (i > n - 1) { count++; return; } for (int w = 0; w < n; w++) { if (check_w(i, w)) { w_place[i] = w; a[i][w] = 0; for (int b = 0; b < n; b++) { if (check_b(i, b)) { b_place[i] = b; a[i][b] = 0; backTrace(i + 1); a[i][b] = 1; } } a[i][w] = 1; } } } private static boolean check_w(int i, int j) { if (a[i][j] == 0) return false; for (int k = 0; k < i; k++) { if (w_place[k] == j || Math.abs(i - k) == Math.abs(w_place[k] - j)) return false; } return true; } private static boolean check_b(int i, int j) { if (a[i][j] == 0) return false; for (int k = 0; k < i; k++) { if (b_place[k] == j || Math.abs(i - k) == Math.abs(b_place[k] - j)) return false; } return true; } } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
