【leetcode】52. N皇后 II（n-queens-ii）（回溯）[困难]

链接

https://leetcode-cn.com/problems/n-queens-ii/

耗时

解题：35 min
题解：7 min

题意

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

思路

根据题意，每行每列只能放一个。所以 dfs 每行，找每 行 可以放的 列，对于每一列所确定的位置，都检查当前位置是否安全（横竖斜都不在攻击范围内），如果安全则选定这个位置，dfs 下一行，直到 dfs 到第 n 行，说明当前的放法就可行，结果+1。

时间复杂度： O ( n ∗ n ! ) O(n*n!) O(n∗n!)

AC代码

class Solution {
private:
    int ans = 0;
    vector<vector<int>> m;
    int n;
public:
    bool CheckSafe(int r, int c) {
        // column row
        for(int i = 0; i < n; ++i) {
            if(m[i][c] == 1 || m[r][i] == 1) {
                return false;        
            }
        }
        // backslash
        for(int x = r-min(r,c), y = c-min(r,c); x < n && y < n; ++x, ++y) {
            if(m[x][y] == 1) {
                return false;
            }
        }
        // forward slash
        for(int x = min(r+min(r,c), n-1), y = c-(x-r); x >= 0 && y < n; --x, ++y) {
            if(m[x][y] == 1) {
                return false;
            }
        }
        return true;
    }
    
    void dfs(int r) {
        if(r == n) {
            ans++;
            return ;
        }
        for(int c = 0; c < n; ++c) {
            if(m[r][c] == 0 && CheckSafe(r, c)) {
                m[r][c] = 1;
                dfs(r+1);
                m[r][c] = 0;
            }
        }
    }
    
    int totalNQueens(int n) {
        this->n = n;
        m.resize(n, vector<int>(n, 0));
        dfs(0);
        return ans;
    }
};