首页 > 搜索 > DFS搜索 > LeetCode-N-Queens II[DFS]
2014
11-19

LeetCode-N-Queens II[DFS]

N-Queens II

Follow up for N-Queens problem.

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

标签: Backtracking
分析

只需要输出解的个数,不需要输出所有解,代码要比上一题简化很多。设一个全局计数器,每找到一个解就增1。

代码1

// LeetCode, N-Queens II
// 深搜+剪枝
// 时间复杂度O(n!),空间复杂度O(n)
class Solution {
public:
    int totalNQueens(int n) {
        this->count = 0;
        this->columns = vector<int>(n, 0);
        this->main_diag = vector<int>(2 * n, 0);
        this->anti_diag = vector<int>(2 * n, 0);

        vector<int> C(n, 0);  // C[i]表示第i行皇后所在的列编号
        dfs(C, 0);
        return this->count;
    }
private:
    int count; // 解的个数
    // 这三个变量用于剪枝
    vector<int> columns;  // 表示已经放置的皇后占据了哪些列
    vector<int> main_diag;  // 占据了哪些主对角线
    vector<int> anti_diag;  // 占据了哪些副对角线

    void dfs(vector<int> &C, int row) {
        const int N = C.size();
        if (row == N) { // 终止条件,也是收敛条件,意味着找到了一个可行解
            ++this->count;
            return;
        }

        for (int j = 0; j < N; ++j) {  // 扩展状态,一列一列的试
            const bool ok = columns[j] == 0 &&
                    main_diag[row + j] == 0 &&
                    anti_diag[row - j + N] == 0;
            if (!ok) continue;  // 剪枝:如果合法,继续递归
            // 执行扩展动作
            C[row] = j;
            columns[j] = main_diag[row + j] =
                    anti_diag[row - j + N] = 1;
            dfs(C, row + 1);
            // 撤销动作
            // C[row] = 0;
            columns[j] = main_diag[row + j] =
                    anti_diag[row - j + N] = 0;
        }
    }
};

相关题目
N-Queens


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.