AcWing 1432. 棋盘挑战
原题链接
中等
作者:
尼古拉斯小布丁
,
2021-03-24 18:32:07
,
所有人可见
,
阅读 303
八皇后问题
#include <iostream>
using namespace std;
const int N = 15;
int n;
bool col[N],dg[N*2],udg[N*2];
int path[N], res;
void dfs(int x){ //表示枚举的行数
if(x>n){
res++;
if(res<=3){
for(int i=1;i<=n;i++)
cout<<path[i]<<" ";
cout<<endl;
}
}
for(int y=1;y<=n;y++){ //枚举每一列
if(!col[y] && !dg[x+y] &&!udg[x-y+n]){
path[x] = y; //放置棋子
col[y]=dg[x+y]=udg[x-y+n]=true; //设置标志
dfs(x+1);
col[y]=dg[x+y]=udg[x-y+n]=false; //恢复标志
path[x] = 0;
}
}
}
int main(){
cin>>n;
dfs(1);
cout<<res<<endl;
return 0;
}