AcWing 3472. 八皇后
原题链接
中等
作者:
编号002
,
2024-04-19 09:34:20
,
所有人可见
,
阅读 2
//dfs得出全部符合题目的路径,这些路径本身(全排列)就是按顺序排好的
//全排列中寻找特殊解
#include<iostream>
using namespace std;
const int N=9;
int path[N];
bool yy[N],up[2*N],low[2*N]; //判重数组
int map[100][N],cnt=1;
void dfs(int u)
{
if(u==8)
{
for(int i=0;i<8;i++)map[cnt][i]=path[i];
cnt++;
return;
}
for(int i=1;i<=8;i++)
{
if(!yy[i]&&!low[u-i+N]&&!up[u+i])
{
path[u]=i;
yy[i]=low[u-i+N]=up[u+i]=1;
dfs(u+1);
yy[i]=low[u-i+N]=up[u+i]=0;
// path[u]=0; //可以省略
}
}
}
int main()
{
int n;
cin>>n;
dfs(0);
while(n--)
{
int m;
cin>>m;
for(int i=0;i<8;i++)cout<<map[m][i];
cout<<endl;
}
return 0;
}