52 lines
1.9 KiB
C++
52 lines
1.9 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 100;
|
||
int a[N], n, ans;
|
||
int b1[N];//列桶
|
||
int b2[N];//正对角线桶
|
||
int b3[N];//反对角线桶
|
||
|
||
//解决：第x行的皇后放在哪里？
|
||
void dfs(int x) {
|
||
if (x == n + 1) {
|
||
//方案数量
|
||
ans++;
|
||
if (ans <= 3) {
|
||
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
|
||
printf("\n");
|
||
}
|
||
return;
|
||
}
|
||
//尝试在第i列放入皇后
|
||
for (int i = 1; i <= n; i++) {
|
||
//因为x上按行一行一行来的，所以不用考虑行的冲突，只需要考虑列、正对角线，反对角线三个方向
|
||
//b2[x+i] 因为同一正角线的位置，行+列是相等的，如果我们设置了 行+列使用过了，
|
||
//那么，其它再检查到同一对角线时，就会发现行+列已使用过
|
||
//b3[x - i + 15] 因为同一反对角线的位置，行-列是相等的，但可能行>列，也可能列>行，
|
||
//这要看它是最长对角线的右上方还是左下方，右上方x>y,左下方x<y
|
||
//为了防止出现负数数组下标，所以，采用了加一个偏移量的办法，这样，不管是大于还是小于，都规划到一个下标大于零的位置上。
|
||
//注意：这里不能使用abs,因为 abs(x-y)与abs(y-x)不是一条反对角线！！！
|
||
//为什么是15？就是因为n的范围是13，大于13即可！
|
||
if (!b1[i] && !b2[x + i] && !b3[x - i + 15]) {
|
||
//标识使用
|
||
a[x] = i;
|
||
//打上标识
|
||
b1[i] = b2[x + i] = b3[x - i + 15] = 1;
|
||
//递归下一行
|
||
dfs(x + 1);
|
||
//解除标识
|
||
b1[i] = b2[x + i] = b3[x - i + 15] = 0;
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//n皇后问题
|
||
cin >> n;
|
||
//放第几行
|
||
dfs(1);
|
||
//输出大吉
|
||
printf("%d\n", ans);
|
||
return 0;
|
||
} |