题解 | #N皇后问题#

class Solution {
private:
    int res = 0;
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int Nqueen(int n) {
        // write code here
        vector<vector<int>> rec(n, vector<int>(n, 0));
        dfs(rec, n, 0);
        return res;
    }
    
    void dfs(vector<vector<int>>& rec, int n, int cur){
        if(cur == n){
            res += 1;
            return;
        }
        
        for(int j=0; j<n; j++){
            bool a = check(rec, n, cur, j);
            if(a){
                rec[cur][j] = 1;
                dfs(rec, n, cur+1);
                rec[cur][j] = 0;
            }
        }
    }
    
    bool check(vector<vector<int>>& rec, int n, int cur_i, int cur_j){
        for(int i=0; i<cur_i; i++){
            if(rec[i][cur_j] == 1){
                return false;
            }
        }
        
        int i=cur_i-1, j=cur_j+1;
        while(i>=0 && j<n){
            if(rec[i][j] == 1){
                return false;
            }
            i--;
            j++;
        }
        
        i=cur_i-1, j=cur_j-1;
        while(i>=0 && j>=0){
            if(rec[i][j] == 1){
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
    
};