51. N-Queens

51. N 皇后

Posted by bbkgl on September 3, 2020

唤起一天明月

照我满怀冰雪

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;
    }
};