AcWing 1432. 棋盘挑战
原题链接
中等
作者:
黑帮大白菜
,
2021-01-22 09:50:52
,
所有人可见
,
阅读 375
八皇后问题(dfs)
#include <iostream>
#include <cmath>
using namespace std;
int f[20], v[20];
int ans, n;
bool OK(int i, int k)
{
for(int j = 1;j < k;j ++)
if(abs(f[j] - i) == abs(k - j)) return false; //通过斜率是否等于1判断对角线方向
return true;
}
void dfs(int k) //按行搜索
{
if(k > n){
ans ++;
if(ans <= 3){
for(int i = 1;i <= n;i ++) cout << f[i] << ' ';
cout << endl;
}
return ;
}
for(int j = 1;j <= n;j ++) //枚举列
{
if(!v[j] && OK(j,k))
{
v[j] = 1;
f[k] = j;
dfs(k+1);
v[j] = 0;
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans << endl;
return 0;
}