Leetcode第52题(N皇后II)

题目描述:

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：n = 1
输出：1

具体思路与上一题N皇后基本一致, 此题直接返回解决方案数量即可。此处就不在多赘述。

class Solution {
    int ans;
    vector<bool> col,dg,udg;
public:
    int totalNQueens(int n) {
        col = vector<bool>(n);
        dg = udg = vector<bool>(2 * n);
        dfs(n, 0);
        return ans;
    }
    void dfs(int n,int x){
        if(x == n){
            ans++;
            return;
        }
        for(int y = 0; y < n; y++){
            if(col[y] || dg[x + y] || udg[y - x + n]) continue;
            col[y] = dg[x + y] = udg[y - x + n] = true;
            dfs(n, x + 1);
            //回退状态
            col[y] = dg[x + y] = udg[y - x + n] = false;
        }
    }
};