AcWing 843. n-皇后问题
原题链接
中等
作者:
永远热爱
,
2021-03-27 10:13:12
,
所有人可见
,
阅读 280
#include<iostream>
using namespace std;
const int N=110;
char str[N][N];
int d[N];
int n;
bool st[N],ag[N],dg[N];
void dfs(int u)
{
if(u==n) //如果走到底就输出
{
for(int i=0;i<n;i++)puts(str[i]);
cout<<endl;
return;
}
for(int i=0;i<n;i++)
{
if(!st[i]&&!ag[i+u]&&!dg[n-u+i]) //这是一层一层递进的,因此每一层都最多只有一个Q 然后判断列与左右斜边
{
str[u][i]='Q';
st[i]=ag[i+u]=dg[n-u+i]=true;
dfs(u+1);
st[i]=ag[i+u]=dg[n-u+i]=false;
str[u][i]='.';
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
str[i][j]='.'; //初始化为 '.';
dfs(0);
return 0;
}