题解 | #N皇后问题#

class Solution {
    vector<int> col, dg, udg;
    int n;
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int Nqueen(int _n) {
        // write code here
        n = _n;
        col = vector<int>(n);
        dg = udg = vector<int>(2 * n);
        return dfs(0);
    }

    int dfs(int x) {
        if (x == n) return 1;
        else {
            int res = 0;
            for (int y = 0; y < n; y++) {
                if (!col[y] && !dg[y - x + n] && !udg[y + x]) {
                    col[y] = dg[y - x + n] = udg[y + x] = true;
                    res += dfs(x + 1);
                    col[y] = dg[y - x + n] = udg[y + x] = false;
                }
            }
            return res;
        }
    }
};

• 思路：递归+三个状态数组
• 使用列、正对角线和负对角线三个数组来维护哪些位置不能放皇后
• 正对角线：y = x + k -> k = y - x 有可能小于0，需要加上n使其变为正数
• 1、遍历每一行
• 2、枚举将皇后放在每一列的位置
• 3、如果当前位置的三个数组值都是false，则继续遍历下一行，直到遍历至末尾
• 时间复杂度：O(n!)
• 空间复杂度：O(n)