凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 52. N-Queens II

分类:algorithm| 发布时间:2016-10-15 15:11:00


题目

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

题意

求出 n 皇后问题的所有解法的个数。

解法

class Solution {
public:
    int totalNQueens(int n) {
        vector<int> flag_col(n, 1), flag_45(2 * n - 1, 1), flag_135(2 * n - 1, 1);
        int num = 0;
        solveNQueens(flag_col, flag_45, flag_135, 0, n, num);
        return num;
    }

private:
    void solveNQueens(vector<int> &flag_col, vector<int> &flag_45, vector<int> &flag_135, int row, int n, int &nums) {
        if (row == n) {
            ++nums;
            return;
        }

        for (int col = 0; col != n; ++col)
            if (flag_col[col] && flag_45[row + col] && flag_135[n - 1 + col - row]) {
                flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 0;
                solveNQueens(flag_col, flag_45, flag_135, row + 1, n, nums);
                flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 1;
            }
    }
};