还是 N 皇后
题目描述
正如题目所说,这题是著名的 $N$ 皇后问题。
输入格式
第一行有一个 $N$。接下来有 $N$ 行 $N$ 列描述一个棋盘,*
表示可放,.
表示不可放。
输出格式
输出方案总数。
样例 #1
样例输入 #1
4
**.*
****
****
****
样例输出 #1
1
提示
$0< n\le14$
题目分析
目的:求出 $N$ 皇后的方案总数。
对于 $N$ 皇后问题,要求是每行、每列有且只有一个棋子,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。并且在本道题目中,还额外对一些位置做了要求,有些位置可以放置棋子,有些位置不能放置棋子。
由于每一行只能放置一个棋子,每列也是只能放置一个棋子,若我们从第一行到最后一行将棋子放置的列号写出,可发现是一个由 $1\sim n$ 的不重复数字组成的数列。所有的排列情况即 $n$ 的全排列,时间复杂度为 $O(n!)$,在题目规模下必然会超时。我们需要寻找优化的方法。
暴搜框架
void dfs(int d){//d-已放置的棋子个数
if(d==n){//已放置n个棋子
//输出
return 0;
}
for(int i=1;i<=n;i++){
if(chk(i)){
//判断(d+1,i)是否可放置
//相关标记处理
dfs(d+1);
//回溯处理
}
}
}
在暴力搜索的过程中,有一个过程是存在重复处理的,就是每一行一列列判断棋盘位置是否可放置棋子的这一步。随着棋子放置个数的增多,棋盘上实际可放置的位置会越来越少,而程序依旧需要 $1\sim n$ 逐个去进行遍历。若能直接定位到未放置的位置,省略了中间遍历寻找的过程,速度自然大大加快。
仔细观察,可发现,实际上每个位置无非两种情况:
- 可以放
- 不能放
列数最多为 $13$ 列,不是很多,我们可以用状态压缩的思想去记录每一列棋子放置情况。另外,位运算操作中有一个技巧,它能跳过低位的 $0$ ,直接定位到最低位的 $1$。它就是 lowbit
操作。
int lowbit(int x){//返回x二进制对应的最低位的1
return x&-x;
}
此时,我们可以将能放的位置处理为 $1$,不能放的处理为 $0$,再利用lowbit
操作即可实现加速的要求。
for(int i=state;i;i-=lowbit(i))//遍历state 中的二进制1
{
int x=lowbit(i);
//......
}
对于本题,还有一个难点在于对角线不能重复,对角线分两条,一条左倾,一条右倾。该如何在二进制状态中描述对角线的影响呢?
仔细观察,对于左倾对角线,在某行 $y$ 列占位,那么影响的是下一行 $y+1$ 列,也就是只要右移一位就好。对应的右倾对角线也只要左移一位就好。
代码实现
#include<bits/stdc++.h>
using namespace std;
int a[15];//每一行对放置位置限制的状压表示
int n,ans,all;
int lowbit(int x){
return x&(-x);
}
void dfs(int d,int col,int L,int R){
//d-已放置的棋子个数/行数 col-棋子放置的列信息的状压表示
//L-棋子放置的左倾对角线信息的状压表示 R-棋子放置的右倾对角线信息的状压表示
if(d==n){//已放置n颗棋子
ans++;//方案数增加
return ;
}
//反转状态,将未放置的设为1,放置的设为0
int vis=all&(~(col|L|R|a[d+1]));
for(int i=vis;i;i-=lowbit(i)){//遍历第d+1行所有能放的位置
int x=lowbit(i);//获取具体列的信息
// 下一个棋子 更新列信息 左倾对角线 右倾对角线
dfs(d+1,col+x,(L+x)>>1,(R+x)<<1);
}
}
int main()
{
char c;
cin>>n;
all=(1<<n)-1;//构造二进制n位都为1的数字
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c;
if(c=='.'){
a[i]|=(1<<(j-1));//将位置信息进行状压
}
}
}
dfs(0,0,0,0);
cout<<ans;
return 0;
}