题解 | #N皇后问题#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 the n
     * @return int整型
     */
     int n;
     vector<bool> col, dg, udg;  // 列 正对角线 反对角线
    int Nqueen(int _n) {
        // write code here
        n = _n;
        col = vector<bool> (n);  // 初始化列的数量
        dg = udg = vector<bool> (2 * n);  // 初始化正反对角线的数量
        return dfs(0);
    }

    int dfs(int u ) {
        if (u == n ) return 1;  // 如果找到了就返回方案数量1
        int res = 0;  // 统计方案数量
        for (int i = 0; i < n; i ++ ) {
            if (!col[i] && !dg[u - i + n] && !udg[u + i]) {  // 如果列、正对角线、反对角线的这个位置没有放过就可以放
                col[i] = dg[u - i + n] = udg[u + i] = true;  // 标记列、正对角线、反对角线都放过了
                res += dfs(u + 1);  // 递归到下一层 然后进行方案数量累加
                col[i] = dg[u - i + n] = udg[u + i] = false;  // 恢复现场
            }
        }
        return res;
    }
};