Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
思路:此题虽然是N皇后问题的变体,但还是可以用N皇后的思路去解决,只是用了一个set来存储合法的皇后
bool isNQueens(vector<int>& res){
for (int i = 0; i < res.size(); i++){
for (int j = i + 1; j < res.size(); j++){
if (i - j == res[i] - res[j] || i - j == res[j] - res[i])return false;
}
}
return true;
}
void dfs_SolveNQueens(vector<int>& res, int pos, set<vector<int>>& tt){
if (pos == res.size()){
if (isNQueens(res)){
tt.insert(res);
}
return;
}
for (int i = pos; i < res.size(); i++){
swap(res[i], res[pos]);
dfs_SolveNQueens(res, pos + 1, tt);
swap(res[i], res[pos]);
}
}
int totalNQueens(int n){
if (n == 0)return 0;
vector<int> temp;
for (int i = 0; i < n; i++)temp.push_back(i);
set<vector<int>> res;
dfs_SolveNQueens(temp, 0, res);
return res.size();
}
思路1可能有重复的计算量
bool safe(vector<int>& res, int c){
for (int i = 0; i < c; i++){
if (res[i] == res[c] || abs(res[i] - res[c] == abs(i - c)))
return false;
}
return true;
}
void dfs_SloveNQueens(int &cnt, vector<int>& res, int n, int c){
if (c == n){
cnt++;
return;
}
for (res[c] = 0; res[c] < n; res[c]++){
if (safe(res, c))dfs_SloveNQueens(cnt, res, n, c + 1);
}
}
int totalNQueens(int n){
vector<int> res(n);
int cnt = 0;
dfs_SloveNQueens(cnt, res, n, 0);
return cnt;
}