C++實(shí)現(xiàn)LeetCode(52.N皇后問題之二)

更新時間：2021年07月15日 17:06:03 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(52.N皇后問題之二),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 52. N-Queens II N皇后問題之二

The n-queens puzzle is the problem of placing nqueens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

這道題是之前那道 N-Queens 的延伸，說是延伸其實(shí)我覺得兩者順序應(yīng)該顛倒一樣，上一道題比這道題還要稍稍復(fù)雜一些，兩者本質(zhì)上沒有啥區(qū)別，都是要用回溯法 Backtracking 來解，如果理解了之前那道題的思路，此題只要做很小的改動即可，不再需要求出具體的皇后的擺法，只需要每次生成一種解法時，計(jì)數(shù)器加一即可，代碼如下：

解法一：

class Solution {
public:
    int totalNQueens(int n) {
        int res = 0;
        vector<int> pos(n, -1);
        helper(pos, 0, res);
        return res;
    }
    void helper(vector<int>& pos, int row, int& res) {
        int n = pos.size();
        if (row == n) ++res;
        for (int col = 0; col < n; ++col) {
            if (isValid(pos, row, col)) {
                pos[row] = col;
                helper(pos, row + 1, res);
                pos[row] = -1;
            }
        }
    }
    bool isValid(vector<int>& pos, int row, int col) {
        for (int i = 0; i < row; ++i) {
            if (col == pos[i] || abs(row - i) == abs(col - pos[i])) {
                return false;
            }
        }
        return true;
    }
};

但是其實(shí)我們并不需要知道每一行皇后的具體位置，而只需要知道會不會產(chǎn)生沖突即可。對于每行要新加的位置，需要看跟之前的列，對角線，及逆對角線之間是否有沖突，所以我們需要三個布爾型數(shù)組，分別來記錄之前的列 cols，對角線 diag，及逆對角線 anti_diag 上的位置，其中 cols 初始化大小為n，diag 和 anti_diag 均為 2n。列比較簡單，是哪列就直接去 cols 中查找，而對角線的話，需要處理一下，如果我們仔細(xì)觀察數(shù)組位置坐標(biāo)的話，可以發(fā)現(xiàn)所有同一條主對角線的數(shù)，其縱坐標(biāo)減去橫坐標(biāo)再加n，一定是相等的。同理，同一條逆對角線上的數(shù)字，其橫縱坐標(biāo)之和一定是相等的，根據(jù)這個，就可以快速判斷主逆對角線上是否有沖突。任意一個有沖突的話，直接跳過當(dāng)前位置，否則對于新位置，三個數(shù)組中對應(yīng)位置都賦值為 true，然后對下一行調(diào)用遞歸，遞歸返回后記得還要還原狀態(tài)，參見代碼如下：

解法二：

class Solution {
public:
    int totalNQueens(int n) {
        int res = 0;
        vector<bool> cols(n), diag(2 * n), anti_diag(2 * n);
        helper(n, 0, cols, diag, anti_diag, res);
        return res;
    }
    void helper(int n, int row, vector<bool>& cols, vector<bool>& diag, vector<bool>& anti_diag, int& res) {
        if (row == n) ++res;
        for (int col = 0; col < n; ++col) {
            int idx1 = col - row + n, idx2 = col + row;
            if (cols[col] || diag[idx1] || anti_diag[idx2]) continue;
            cols[col] = diag[idx1] = anti_diag[idx2] = true;
            helper(n, row + 1, cols, diag, anti_diag, res);
            cols[col] = diag[idx1] = anti_diag[idx2] = false;
        }
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(52.N皇后問題之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)N皇后問題之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: