[USACO1.5] 八皇后 Checker Challenge
2025年2月26日小于 1 分钟
#include <bits/stdc++.h>
using namespace std;
int n, cnt;
int ans[15]; //ans[x]:第x层放在了第ans[x]列
//当前考虑第step层放在第几列
void dfs(int step)
{
if (step > n)
{
cnt++;
if (cnt <= 3)
{
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
cout << "\n";
}
return;
}
for (int i = 1; i <= n; i++)
{
//判断是否冲突
bool flag = true;
for (int j = 1; j <= step - 1; j++)
{
//(step,i) (j,ans[j])
if (step == j || i == ans[j] ||
step - i == j - ans[j] || step + i == j + ans[j])
{
flag = false;
break;
}
}
if (flag)
{
ans[step] = i;
dfs(step + 1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
dfs(1);
cout << cnt << endl;
return 0;
}