题解 | #N皇后问题#(递归回溯)

定义三个访问数组，列不能重复访问，正斜线不能重复访问， 反斜线不能重复访问。

其中正斜线用行下标减列下标唯一表示 总计2*N-1个，因为有负数结果，所以平移N-1位存储。

反斜线由行下标加列下标表示，也是2*N-1个。

class Solution {
public:
    int N;
    int res=0;
    int Nqueen(int n) {
        // write code here
        if(n==1) return 1;
        N = n;  // 写成了 int N = n， 全局变量已经声明了，又定义了一次，一直结果不对  
        vector<bool> visited(n, false);  // 列访问数组
        vector<bool> xie_visited(2*N-1, false);  // 正斜线访问数组
        vector<bool> xie2_visited(2*N-1, false);  // 反斜线访问数组
        dfs(0, visited, xie_visited, xie2_visited);
        return res;
    }
    void dfs(int i, vector<bool> &visited, vector<bool> &xie_visited, vector<bool> &xie2_visited){
        if(i == N) {res++; return;}
        for(int j=0; j < N; j++){
            if(!visited[j] && !xie_visited[i-j+N-1] && !xie2_visited[i + j]){
                visited[j] = true;  // 标记访问
                xie_visited[i-j + N - 1 ]= true;
                xie2_visited[i + j] = true;
                dfs(i+1, visited, xie_visited, xie2_visited);
                visited[j] = false;  // 回溯
                xie2_visited[i + j] = false;
                xie_visited[i- j + N - 1] = false;
            }
        }
    }
};

全局变量和局部变量不能命名冲突，否则结果都不知道为什么错