AcWing 843. n-皇后问题
原题链接
中等
#include<iostream>
#include<algorithm>
using namespace std;
const int N=22;
vector<vector<char>> f(N,vector<char>(N));
bool stx[N],stl[N],str[N];
int n;
//vector<vector<char>> res;
void bfs(int y)
{
if(y==n)
{ for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<f[i][j];
cout<<endl;}
cout<<endl;
return ;
}
for(int x=0;x<n;x++)
if(!stx[x]&&!stl[y+x]&&!str[y-x+n])
{ f[y][x]='Q';
stx[x]=true;
stl[y+x]=true;
str[y-x+n]=true;
bfs(y+1);
f[y][x]='.';
stx[x]=false;
stl[y+x]=false;
str[y-x+n]=false;}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
f[i][j]='.';
bfs(0);
return 0;
}