题目描述
$n$-皇后问题是将 $n$ 个皇后放在 $n*n$ 的棋盘上,使得皇后不能相互攻击到。
给定一个整数 $n$,返回所有 $n$-皇后问题的不同方案数。
样例
输入:
4
输出:
2
解释:4-皇后问题一共有两种合法方案,如下所示:
[
[".Q..", // 方案1
"...Q",
"Q...",
"..Q."],
["..Q.", // 方案2
"Q...",
"...Q",
".Q.."]
]
算法
(暴力枚举) $O(n!)$
此题解法和 N-Queens 完全相同。只是将记录方案,改成记录方案数。
C++ 代码
class Solution {
public:
int ans;
vector<bool> row, col, diag, anti_diag;
int totalNQueens(int n) {
row = col = vector<bool>(n, false);
diag = anti_diag = vector<bool>(2 * n, false);
ans = 0;
dfs(0, 0, 0, n);
return ans;
}
void dfs(int x, int y, int s, int n)
{
if (y == n) x ++ , y = 0;
if (x == n)
{
if (s == n) ++ ans;
return ;
}
dfs(x, y + 1, s, n);
if (!row[x] && !col[y] && !diag[x + y] && !anti_diag[n - 1 - x + y])
{
row[x] = col[y] = diag[x + y] = anti_diag[n - 1 - x + y] = true;
dfs(x, y + 1, s + 1, n);
row[x] = col[y] = diag[x + y] = anti_diag[n - 1 - x + y] = false;
}
}
};
y总这里遍历完 坐标(x,y)为什么不用通用的往上下左右四个方向扩展的方法而是从左往右从上到下的扫描法呢? 仅仅是用了启发式 搜索进行了剪枝吗? 原谅我太菜我想找到通用的搜索模板来做hhh
啊这里没有启发式剪枝。只要能把所有格子枚举一遍即可,不论什么顺序都是可以的,所以这里就随便用了一个最简单的遍历方式hh
请问灿哥,这里主对角线和副对角线为什么有2n条,我怎么感觉是2n-1条,不过似乎对结果影响不大?
对角线都只有 $2n-1$ 条,只不过开判重数组的时候多开了1个位置而已hh
哈哈,无伤大雅
优化点:可以缺少row
可以的。这题可以调整搜索顺序:依次枚举每一行的皇后该放到哪个位置,会快很多。
嗯嗯
请问这题还可以继续优化吗?在牛客网的oj上说超时了
可以考虑用位运算,或者dancing links继续优化~