AcWing 843. n-皇后问题
原题链接
中等
作者:
ls131
,
2021-01-20 11:39:02
,
所有人可见
,
阅读 353
#include<bits/stdc++.h> //dfs 深度优先搜索 先搜到挨个分支的叶子节点然后 依次递归返回
using namespace std;
const int N =20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N]; //1直接拿下标对应行2每行每列对角线与反对角线3用截距作为对角线关键字 4遇到负值加偏移量改变其值域
void dfs(int u){
if(u==n){
for(int i=0;i<n;i++) puts(g[i]);
puts("");
return; //递归出口
}
for(int i=0;i<n;i++)
if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){
g[u][i]='Q';
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1);
col[i]=dg[u+i]=udg[n-u+i]=false;
g[u][i]='.';
}
}
int main(){
cin>>n;
for(int i =0;i<n;i++)
for(int j=0;j<n;j++)
g[i][j]='.';
dfs(0);
return 0;
}