题目大意:给定n,求问对于n*n的棋盘,放置皇后问题的解的数量。

题目描述

Follow up for N-Queens problem.

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

alter text

算法描述

本题为#51 N-Queens的变形版本,其算法本质上并没有什么变化。唯一和#51不同的是,本题只需要返回解的个数,所以我们只需要在51题的基础上进行一点小的改动即可。

代码

class Solution {
    int ret;
public:
    int totalNQueens(int n) {
        // 构造用于判断攻击的数组
        vector<bool> column(n, false);
        vector<bool> cross1(n * 2 - 1, false);
        vector<bool> cross2(n * 2 - 1, false);
        // 初始化解的计数器
        ret = 0;
        // 回溯求解所有的方案
        backtracking(0, n, column, cross1, cross2);
        // 返回所有答案
        return ret;
    }
    void backtracking(int i, int n, vector<bool>& column, vector<bool>& cross1, vector<bool>& cross2) {
        // 判断是否已经枚举完了每一行的皇后位置,如果是,说明已经找到了一组解
        if (i == n) {
            // 解的计数器加1
            ++ret;
        }
        else {
            // 否则枚举当前行皇后放置的位置
            for (int j = 0; j < n; j++) {
                // 判断是否会和之前放置的皇后产生列上的冲突
                if (column[j]) continue;
                // 判断是否会和之前放置的皇后产生第一种对角线上的冲突
                if (cross1[i + j]) continue;
                // 判断是否会和之前放置的皇后产生第二种对角线上的冲突
                if (cross2[i - j + n - 1]) continue;
                // 如果都不产生冲突,说明当前方案合法,对状态进行修改并递归的枚举下一行的放置方案
                column[j] = true; cross1[i + j] = true; cross2[i - j + n - 1] = true;
                backtracking(i + 1, n, column, cross1, cross2);
                // 回溯,消去产生的修改
                column[j] = false; cross1[i + j] = false; cross2[i - j + n - 1] = false;
            }
        }
    }
};

登录发表评论 注册

反馈意见