题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n
的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。
样例
示例1
输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例2
输入:n = 1
输出:1
DFS(按行遍历)
C++ 代码
class Solution {
public:
int res = 0;
vector<bool> col, d, ud;
int totalNQueens(int n) {
col = vector<bool>(n);
d = ud = vector<bool>(n * 2);
dfs(0, n);
return res;
}
void dfs(int u, int n)
{
if (u == n)
{
res ++;
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, n);
col[i] = d[u + i] = ud[u - i + n] = false;
}
}
};