题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。
样例
示例 1:
输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:1
算法1
(递归)
类似n + n - 1 + n - 2 + ....在递归函数中新建res
层层递归,最终返回res
时间复杂度
参考文献
C++ 代码
class Solution {
public:
vector<bool> udg, dg, col;
int n;
int totalNQueens(int _n) {
n = _n;
dg = udg = vector<bool> (2 * n);
col = vector<bool> (n);
return dfs(0);
}
int dfs(int u){
if (u == n){
return 1;
}
int res = 0;
for (int i = 0; i < n; i ++ ){
if (!dg[i - u + n] && !udg[i + u] && !col[i]){
dg[i - u + n] = udg[i + u] = col[i] = true;
res += dfs(u + 1);
dg[i - u + n] = udg[i + u] = col[i] = false;
}
}
return res;
}
};