蓝桥杯 2021/11/5 2n皇后

  给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。

 

  进行连续的两次n皇后即2n皇后。如:① 1  1  1  1

                                                                     ② 1  1  1  1

                                                                     ③ 1  1  1  1

                                                                     ④ 1  1  1  1

  先插入黑皇后,从①[0]开始遍历,到②[x]~④[x],回溯,全符合条件后再进行白皇后的判断。

 

  代码:

 1 import java.util.Scanner;
 2 public class Main {
 3     static int bQ=2;
 4     static int wQ=3;
 5     static int count=0;
 6     static int white[];
 7     static int black[];
 8     static int arr[][];
 9     public static void main(String[] args) {
10         Scanner sc=new Scanner(System.in);
11         int n=sc.nextInt();
12         arr=new int[n][n];
13         white=new int[n];
14         black=new int[n];
15         for(int i=0;i<n;i++){
16             for(int j=0;j<n;j++){
17                 arr[i][j]=sc.nextInt();
18             }
19         }
20         dfs(black,bQ,0);
21         System.out.println(count);
22     }
23     private static void dfs(int[] Arr,int color,int n){
24         if(n==Arr.length){
25             if(color==wQ) {
26                 count++;
27             }
28             else if(color==bQ){
29                 dfs(white,wQ,0);
30             }
31             return;
32         }
33         for(int i=0;i< white.length;i++){
34             if(arr[n][i]==1&&test(Arr,i,n)){
35                 arr[n][i]=color;
36                 Arr[n]=i;
37                 dfs(Arr,color,n+1);
38                 arr[n][i]=1;
39             }
40         }
41     }
42     private static boolean test(int arr[],int line,int high){
43         for(int i=0;i<high;i++){
44             if(arr[i]==line){
45                 return false;
46             }
47             if(arr[i]+i==line+high){
48                 return false;
49             }
50             if(arr[i]-i==line-high){
51                 return false;
52             }
53         }
54         return true;
55     }
56 }

  该dfs为c语言网的解。明天试试课本的dfs代码,,

上一篇:确定概率的一些方法


下一篇:【ybtoj高效进阶 21286】等差数列(数学)(分类讨论)