AcWing 843. n-皇后问题
原题链接
中等
作者:
minux
,
2020-04-25 17:29:48
,
所有人可见
,
阅读 542
#include <bits/stdc++.h>
using namespace std;
// N-Queen问题,解决思路和全排列类似
const int N=20;
int n;
char G[N][N];
bool COL[N]; // 列是否可以使用
bool DG[N]; // 主对角线可以使用
bool UDG[N]; // 副对角线是否可以使用
// 对行进行dfs搜索
void dfs(int row){
if(row==n){
for(int i=0; i<row; ++i) cout<<G[i]<<endl;
cout<<endl;
}
for(int i=0; i<n; ++i){
if(!COL[i]&&!DG[row+i]&&!UDG[n-row+i]){
G[row][i]='Q';
COL[i]=DG[row+i]=UDG[n-row+i]=true;
dfs(row+1);
COL[i]=DG[row+i]=UDG[n-row+i]=false;
G[row][i]='.';
}
}
}
int main(){
cin>>n;
memset(G, 0x00, sizeof G);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j)
G[i][j]='.';
}
dfs(0);
return 0;
}