AcWing 843. n-皇后问题
原题链接
中等
作者:
B1ackGod
,
2021-01-11 11:31:55
,
所有人可见
,
阅读 415
思路
- 用二维数组存储图
- 递归推进每一行,例如第一次递归皇后放(1,1),那么下一层递归就是进入第二行放皇后
- 因此必定不处于同一行,所以我们的限制条件就是判断列、对角线、反对角线是否合法。
- 递归结束的条件就是,摆放到最后一行即u=n时(下标从0开始,最后一行即n-1)。递归结束就开始打印棋盘图。
- 数组模拟列、对角线、反对角线,即在图上画一个直角坐标轴,它们分别就是y,y-x=0即y-x+n(避免下标为零),y+x=0。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=20;
int n;
char g[N][N];
//判断列、对角线、反对角线是否合法。任意两个皇后都不能处于同一行、同一列或同一斜线上。
bool col[N],dg[N],udg[N];
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;
}