[蓝桥杯][基础训练]2n皇后问题

Description

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

Input

输入的第一行为一个整数n,表示棋盘的大小。
  

接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。

Output

输出一个整数,表示总共有多少种放法。

Sample Input

4

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

Sample Output

2


 1 #include<iostream>
 2 #include<cmath> 
 3 using namespace std;
 4 int n;
 5 int map[103][103];//存储棋盘信息 
 6 int pos_black[103];//存储黑皇后的行位置 
 7 int pos_white[103]; //存储白皇后的行位置 
 8 int ans;
 9 int check_white(int cur){//检验白皇后的位置是否符合要求 
10     for(int i=1;i<cur;i++){//cur列之前的列都和cur列比较 
11         if(pos_white[i]==pos_white[cur]||abs(i-cur)==abs(pos_white[i]-pos_white[cur]))
12             //检验是否在同一行或者对角线上 
13             return 0;
14     }
15     return 1;
16 }
17 int check_black(int cur){//检验黑皇后的位置是否符合要求,和白皇后一样 
18     for(int i=1;i<cur;i++){
19         if(pos_black[i]==pos_black[cur]||abs(i-cur)==abs(pos_black[i]-pos_black[cur]))
20             return 0;
21     }
22     return 1;
23 }
24 void dfs_white(int cur){//依次放置白皇后 
25     if(cur==n+1){//如果已经放置n个了,答案+1 
26         ans++;
27         return;
28     }
29     for(int i=1;i<=n;i++){
30         if(map[i][cur]==0)//看地图条件是否符合 
31             continue;
32         if(pos_black[cur]==i)//看有没有与黑皇后的位置重合 
33             continue;
34         pos_white[cur]=i;//将白皇后放在第i行第cur列 
35         if(check_white(cur))//如果刚才放置的这个白皇后符合要切 
36             dfs_white(cur+1);//就开始放置下一个白皇后        
37     }
38 }
39 void dfs_black(int cur){//依次放置黑皇后 
40     if(cur==n+1){//如果已经放置n个了 
41         dfs_white(1);//开始放置白皇后 
42         return;
43     }
44     for(int i=1;i<=n;i++){
45         if(map[i][cur]==0)//如果地图符合条件 
46             continue;
47         pos_black[cur]=i;//将黑皇后放在第i行第cur列 
48         if(check_black(cur))//如果刚放置的黑皇后符合条件 
49             dfs_black(cur+1);//放置下一个黑皇后    
50     }
51 }
52 int main(){
53     cin>>n;
54     for(int i=1;i<=n;i++){
55         for(int j=1;j<=n;j++){
56             cin>>map[i][j];
57         }
58     }
59     dfs_black(1);//开始放置黑皇后 
60     cout<<ans;//输出 
61     return 0;
62 }

 

其实先放置黑皇后和白皇后都一样,本文以先放置黑皇后为例,
这样的话,放置白皇后的时候要注意,不能放在黑皇后上。
黑皇后放置完n个后,开始放置白皇后,白皇后放置完n个后,答案数加一,这是一次大循环
这里是一列一列的放,所以同一列一定不会有重复的,
只需判断 行 和 对角线 是否有重复的就行了
另外,其实哪个叫行哪个叫列都无所谓,你分得清就行




上一篇:《组合数学》学习笔记 之 特殊计数序列


下一篇:CF57C Array