LeetCode 52. N-Queens II
原题链接
困难
作者:
Rayhh
,
2021-01-17 22:35:10
,
所有人可见
,
阅读 379
C++ 代码
class Solution {
public:
int ans = 0, n;
vector<bool> col, d, ud;
int totalNQueens(int _n) {
// n皇后问题
// 将n个皇后放到n*n的棋盘上,使之不能相互攻击到
// 不能相互攻击定义:不能同一行、同一列、同一对角线。
// 依次枚举每一行皇后的位置
// 条件:每一列只能有一个皇后(列状态:col[N]), 、
// 每条斜线只能一个皇后(状态d[2n-1], ud[2n-1], 因为正反两个斜线,判断是否在同一个斜线: x+y, y-x+n)
// 坐标原点:左上角。行就是y,列就是x。
// 正斜线方程:y=-x+0,y=-x+1,y=-x+2,y=-x+3.....y=-x+2(n-1),一共是2(n-1)+1种情况,判断当前是第几种情况:y+x
// 反斜线方程: y=x+(n-1),y=x+(n-2).....y=x...y=x-(n-1),一共是2n-1种情况,判断当前是第几种情况:y-x+n。
n = _n;
col = vector<bool>(n);
d = ud = vector<bool> (n * 2);
dfs(0);
return ans;
}
void dfs(int u) {
// 当遍历到第n行
if (u == n) {
ans ++;
return;
}
for (int i = 0; i < n; i++) {
if (!col[i] && !d[u + i] && !ud[u - i + n]) {
col[i] = d[u+i] = ud[u - i + n] = true;
dfs(u + 1);
col[i] = d[u + i] = ud[u - i + n] = false;
}
}
}
};
虽然程序能正常运行出结果,但是
dfs
函数for
循环中,ud[u - i + n]
应该改成ud[u - i + n - 1]
才对吧。