概述
就是搜索嘛,判断行列和所在对角线,关键就在于快速判断这三种状态是否都允许放数字,
我看题解都是用的数组,补上状态压缩的优化吧。
其实就是把原本用数组记录的状态,转换成二进制,合并成大小为0~(2^n)的数字表示,
比如第一行,第二行,分别在第5列和第3列放数字,那么
对于即将放数字的第三行,
列: 001010
左对角线: 011000
右对角线: 000100
有1的地方相当于是不能放的,没有1就是可以放,于是就通过三个数字愉快的记录了我们需要的状态。
好处是代码短,位运算速度稍快,坏处就是刚接触不太熟悉,
其实和原本的数组记录很接近。
代码
#include <iostream>
using namespace std;
int n,cnt=0;
int res[20];
void dfs(int s,int s1,int s2,int x){
if(x==n){
cnt++;
if(cnt<=3){
for(int i=0;i<n;i++) cout<<res[i]+1<<" ";
cout<<endl;
}
return ;
}
for(int i=0;i<n;i++){
if((s | s1 | s2) & (1<<i)) continue; //判断和三个状态是否有冲突
res[x]=i;
dfs(s|(1<<i), (s1|(1<<i))<<1 ,(s2|(1<<i))>>1,x+1);//维护三个状态
res[x]=0;
}
}
int main(){
cin>>n;
dfs(0,0,0,0);
cout<<cnt<<endl;
}