AcWing 1432. 棋盘挑战
原题链接
中等
作者:
wyf
,
2021-01-22 10:24:34
,
所有人可见
,
阅读 333
八皇后问题:按行枚举,每次如果选则将该列该对角线和反对角线打上标记即可
#include<iostream>
#include<vector>
using namespace std;
const int N=15;
char g[N][N];
bool col[N],dg[2*N],udg[2*N];
vector<int> path;
int n,res,cnt;
void dfs(int u){
if(u==n){
res++;
cnt++;
if(cnt<=3){
for(int i=0;i<path.size();i++)cout<<path[i]<<' ';
cout<<endl;
}
return ;
}
for(int i=0;i<n;i++){
if(!col[i]&&!dg[i+u]&&!udg[n+i-u]){
col[i]=true;
dg[i+u]=true;
udg[n+i-u]=true;
path.push_back(i+1);
dfs(u+1);
path.pop_back();
udg[n+i-u]=false;
dg[i+u]=false;
col[i]=false;
}
}
}
int main(){
cin>>n;
dfs(0);
cout<<res<<endl;
return 0;
}