Leetcode | C++ 52-N-Queens II

題目分析：

經典的

NPC

問題——N皇後。給出一個數字

N

，要求在

N*N

大小的棋盤之中擺放

N

個皇後，并要求皇後之前彼此不能攻擊到。僅需算出合法的棋盤布局數目即可。

解題思路:

與

#51

類似，但已不需輸出每種合法的棋盤布局的具體擺放，僅需計數即可。

參照

#51

的解法二，使用與主對角線平行的直線的标記、與次對角線平行的直線的标記以及列的标記來判斷目前行的棋子能夠落在哪一個位置。得到一種合法的擺放情況，将計數值加一即可，整體時間複雜度不變。

class Solution {
public:
     int totalNQueens(int n) {
        int cnt = 0;
        col.resize(n, true);
        left_dia.resize(2*n, true);
        right_dia.resize(2*n, true);
        try_to_solve(0, n, cnt);
        return cnt;
    }
private:
    void try_to_solve(int row, int sz, int &cnt)
    {
        if(row == sz)
        {
            cnt++;
            return;
        }
        for(int i=0;i<sz;i++)
            if(col[i]&& left_dia[row+i]&& right_dia[row-i+sz])//檢查目前前是否可放
            {