AcWing 843. n-皇后问题
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
const int N = 9 + 10;
char g[N][N];
int col[3 * N], zdj[3 * N], fdj[3 * N];
int n;
void queen(int x) {
if (x == n) {
for (int i = 0; i < n; i++) printf("%s\n", g[i]);
puts("");
return;
}
// 列:y = 0 -> col[y]
// 正对角线:x - y = 0 -> zdj[x - y]
// 反对角线:x + y = 0 -> fdj[x + y]
// 由于x - y 最小值为1 - n 可能为负数 而索引不能为负数 所以增加n - 1 即:
// 列:y = 0 -> col[y + n - 1]
// 正对角线:x - y = 0 -> zdj[x - y + n - 1]
// 反对角线:x + y = 0 -> fdj[x + y + n - 1]
for (int y = 0; y < n; y++) {
if (!col[y + n - 1] && !zdj[x - y + n - 1] && !fdj[x + y + n - 1]) {
g[x][y] = 'Q';
col[y + n - 1] = zdj[x - y + n - 1] = fdj[x + y + n - 1] = 1;
queen(x + 1);
g[x][y] = '.';
col[y + n - 1] = zdj[x - y + n - 1] = fdj[x + y + n - 1] = 0;
}
}
}
int main() {
scanf("%d", &n);
// 初始化g[][]全部为'.'
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j] = '.';
queen(0); // 当前枚举到第0行
return 0;
}