题解 | #N皇后问题#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int res = 0;
    bool check(vector<int> vec, int x, int y){
        // 如果在同一列，即vec中存在相同的数是不行的，另外要确保是在不同的斜线上
        for(int i = 0; i < vec.size() - 1; i++){
            if(y == vec[i] || y - x == vec[i] - i - 1 || x + y == vec[i] + i + 1) return false;
        }
        return true;
    }
    void cal(vector<int>& vec, int n){
        // 可以不在这里做检查，但是当vec的size为4的时候就可以res++
        if(vec.size() == n) {
            res++;
            return;
        }

        for(int i = 0; i < n; i++){
            vec.push_back(i+1);
            if(check(vec, vec.size(), i+1)) cal(vec, n);
            vec.pop_back();
        }
    }
    int Nqueen(int n) {
        // write code here
        // 主要思路---采用回溯算法，使用一个数组记录每个节点所在的位置
        // ---- 在每次递归回溯前都要进行一次判断，可以通过节点所在的情况进行判断
        vector<int> vec;
        cal(vec, n);
        return res;
    }
};

清晰明了的递归思路