唤起一天明月
照我满怀冰雪
N皇后，我记得当时八皇后我也是暴力做的，所以这次想到的也是暴力。
然后发现暴力也没问题。。。
计算是否能够攻击到：
- 是否同一行同一列
- 是否在同一条45度斜线上（直接
x1 - x2 == y1 - y2）即可
class Solution {
private:
void dfs(vector<string> &g, int row, int n, vector<int> &pre_cols, vector<vector<string>> &ans) {
if (row == n) {
ans.push_back(g);
return ;
}
for (int col = 0; col < n; col++) {
bool flag = true;
for (int r = 0; r < row; r++) {
int l = pre_cols[r];
if (l == col) flag = false;
else if (abs(r - row) == abs(l - col)) flag = false;
}
if (flag) {
g[row][col] = 'Q';
pre_cols[row] = col;
dfs(g, row + 1, n, pre_cols, ans);
pre_cols[row] = -1;
g[row][col] = '.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
string temp;
for (int i = 0; i < n; i++) temp.push_back('.');
vector<vector<string>> ans;
vector<string> g(n, temp);
vector<int> pre_cols(n, -1);
dfs(g, 0, n, pre_cols, ans);
return ans;
}
};
