核心问题就是一个回溯算法, 并不困难另一个问题在于如何简单有效的判断住对角线和副对角线以及行列上不存在冲突的问题
行冲突在递归中使用depth变量(等同于row)解决了列冲突使用col数组解决每一条主对角线上的数字相加的结果是一样的, 会有2n-1主对角线每一条副对角线上的数字相减的结果是一样的
class Solution {
public:
vector<int> tmp;
vector<vector<string>> ans;
vector<vector<string>> solveNQueens(int n) {
vector<int> col(n, 0);
vector<int> main(2*n - 1, 0);
vector<int> sub(2*n - 1, 0);
dfs(0, n, col, main, sub, tmp, ans);
return ans;
}
void dfs(int depth, int n, vector<int>&col, vector<int>& main, vector<int>& sub, vector<int>& tmp, vector<vector<string>>& ans) {
if (depth == n) {
vector<string> t = convert(tmp, n);
ans.push_back(t);
return;
}
for (int i = 0; i < n; i++) {
if (!col[i] && !main[depth + i] && !sub[depth - i + n - 1]) {
col[i] = 1;
main[depth+i] = 1;
sub[depth - i + n - 1] = 1;
tmp.push_back(i);
dfs(depth + 1, n, col, main, sub, tmp, ans);
tmp.pop_back();
col[i] = 0;
main[depth+i] = 0;
sub[depth - i + n - 1] = 0;
}
}
}
vector<string> convert(vector<int> tmp, int n) {
vector<string> ans;
for (int i = 0; i < tmp.size(); i++) {
string s(n, '.');
s[tmp[i]] = 'Q';
ans.push_back(s);
}
return ans;
}
};
Processed:
0.008, SQL:
8
