题目

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

分析

这题较上一题甚至更简单了。只需要修改递归收敛的地方，将原来的保存当前棋盘改为数量加1即可。另外还删掉了一些多余的变量。

实现

class Solution {
public:
    int totalNQueens(int n) {
        vector<bool>  col(n, false), md(2*n-1, false), cd(2*n-1, false);
        return solve(0, n, col, md, cd);
    }
private:
    int solve(int i, int n, vector<bool> &col, vector<bool> &md, vector<bool> &cd){
        if(i==n) return 1;
        int ans=0;
        for(int j=0; j<n; j++){
            if(col[j] || md[i-j+n-1] || cd[i+j]) continue;
            col[j] = true;
            md[i-j+n-1] = true;
            cd[i+j] = true;

            ans += solve(i+1, n, col, md, cd);
            col[j] = false;
            md[i-j+n-1] = false;
            cd[i+j] = false;
        }
        return ans;
    }
};

思考

这题中，还将原来的nleft变量改为i变量，含义由原来的剩余皇后数目改为当前行数，这样程序更加清晰。