原题链接:Acwing 3472. 八皇后
#include <bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int p[1010];
bool f[1010];
vector<int> res[100];
int num=0;
void n_queen(int index)
{
if(index==9)
{
num++;
for(int i=1;i<=8;i++)
{
res[num].push_back(p[i]);
}
return ;
}
for(int x=1;x<=8;x++)//第x行
{
if(f[x]==false)//如果第x行还没有皇后
{
bool flag=true;//表示当前皇后不会和之前的皇后冲突
for(int pre=1;pre<index;pre++)//遍历之前的皇后
{//第index列皇后的行号为x,第pre列皇后的行号为p[pre]
if(abs(index-pre)==abs(x-p[pre]))
{
flag=false;//当前行与之前的皇后在同一对角线,冲突
break;
}
}
if(flag)//如果可以把皇后放在x行
{
p[index]=x;//令第index列皇后的行号为x
f[x]=true;//标记第x行被占用
n_queen(index+1);//递归处理第index+1行的皇后
f[x]=false;//递归完毕,还原第x行为未占用
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
n_queen(1);
while(n--)
{
int b;
cin>>b;
for(int i=0;i<8;i++)
{
cout<<res[b][i];
}
cout<<endl;
}
return 0;
}