题解 | #N皇后问题#

#include <algorithm>
#include <unordered_set>
#include <vector>
class Solution {
  public:
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    // 该题意味每行必须都有一个皇后
    // 可变数组 未放入皇后的禁区
    vector<int> unRoad1,unRoad2;
    vector<int> unCol;
    int res = 0;
    int Nqueen(int n) {
        // write code here
        compute(0, n);
        return res;
    }
    bool find(int key,vector<int> vec){
        vector<int>::iterator rest= std::find(vec.begin(),vec.end(),key);
        if(rest==vec.end()) return false;
        return true;
    }
    void compute(int i, int n) {
        // 如果访问完了n行，意味着把个皇后插入进去了
        int y = 0;
        if (i == n) {
            res++;
        } else {
            //把第i行的所有元素进行深度优先遍历
            for (int j = 0; j < n; j++) {
                // 接下来的皇后不能触碰已经存在皇后的行、列、对角线
                if (!find(j,unCol)&&!find(i-j, unRoad1)&&!find(i+j, unRoad2)) {
                    // 当前顶点符合要求，把他的行、列、对角线加入集合
                    unCol.push_back(j);
                    unRoad1.push_back(i - j);
                    unRoad2.push_back(i + j);
                    //回溯
                    compute(i + 1, n);
                    // 深度遍历改点后，擦除痕迹，继续遍历第i行其他元素
                    unCol.pop_back();
                    unRoad1.pop_back();
                    unRoad2.pop_back();
                }
            }
        }
        return;
    }
};