题意
求出可以摆放
n
<script type="math/tex" id="MathJax-Element-5">n</script>个皇后的棋盘方案数
思路
和上一题51. N-Queens一样，只不过是要求方案数.
代码
class Solution {
public:
int totalNQueens(
int n) {
vector<int>loc;
for(
int i =
0; i < n; i++){
loc.push_back(-
1);
}
int ans =
0;
DFS(loc,
0, n, ans);
return ans;
}
private:
void DFS(
vector<int>& loc,
int id,
int n,
int& ans){
if(id == n){
ans++;
return ;
}
for(
int i =
0; i < n; i++){
int flag =
0;
for(
int j =
0; j < id; j++){
if((loc[j] == i) || (id + i == loc[j] + j) || (i - loc[j] == id - j)){
flag =
1;
break;
}
}
if(flag)
continue;
loc[id] = i;
DFS(loc, id +
1, n, ans);
loc[id] = -
1;
}
}
};
