AcWing 1432. 棋盘挑战
原题链接
中等
作者:
Bear_King
,
2021-01-24 18:30:10
,
所有人可见
,
阅读 323
八皇后
全排列解法
DFS+回溯
#include<iostream>
using namespace std;
#define N 15
int n,count;
int g[N];
bool col[N],dg[N*2],udg[N*2];
void dfs(int x)
{
if(x > n)
{
count ++;
if(count <= 3)
{
for(int i = 1;i <= n;i ++) printf("%d ",g[i]);
puts("");
}
return;
}
else
{
for(int y = 1;y <= n;y ++)
if(!col[y] && !dg[y+x] && !udg[n-y+x])
{
g[x] = y;
col[y] = dg[y+x] = udg[n-y+x] = true;
dfs(x+1);
col[y] = dg[y+x] = udg[n-y+x] = false;
g[x] = 0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",count);
return 0;
}