一.題目

N-Queens II

My Submissions Total Accepted: 35494 Total Submissions: 96158 Difficulty: Hard

Follow up for N-Queens problem.

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

Show Tags Show Similar Problems Have you met this question in a real interview? Yes No

Discuss

二.解題技巧

這道題和普通的N皇後問題是一樣的，只不過這個是輸出可能存在的情況的個數，過程是一樣的，至少返回值不一樣而已。

三.實現代碼

#include 
#include 
#include 

using std::string;
using std::vector;

class Solution
{
private:
    void DFS(int n_Index, vector> &State, int &Result)
    {
        if (n_Index == State.size() - 1)
        {
            for (int Index = 0; Index < State.size(); ++Index)
            {
                if (State[n_Index][Index] == 1)
                {
                    Result++;
                    break;
                }
            }
            return;
        }

        for (int Index = 0; Index < State.size(); ++Index)
        {
            if (State[n_Index][Index] == 1)
            {
                SetStatue(n_Index, Index, 1, State);
                DFS(n_Index + 1, State, Result);
                SetStatue(n_Index, Index, -1, State);
            }
        }

    }

    void SetStatue(int n_Index, int Index, int Value, vector> &State)
    {
        // col
        for (int ColIndex = Index; ColIndex < State.size(); ++ColIndex)
        {
            State[n_Index][ColIndex] += Value;
        }

        // row
        for (int RowIndex = n_Index; RowIndex < State.size(); ++RowIndex)
        {
            State[RowIndex][Index] += Value;
        }

        int RowIndex = n_Index + 1;
        int ColIndex = Index - 1;
        while(RowIndex < State.size() && ColIndex >= 0)
        {
            State[RowIndex][ColIndex] += Value;
            RowIndex++;
            ColIndex--;
        }

        RowIndex = n_Index + 1;
        ColIndex = Index + 1;
        while (RowIndex < State.size() && ColIndex < State.size())
        {
            State[RowIndex][ColIndex] += Value;
            RowIndex++;
            ColIndex++;
        }

    }

public:
    int totalNQueens(int n)
    {
        int Result = 0;

        vector TmpStatues(n, 1);
        vector> State(n, TmpStatues);

        if (n == 0)
        {
            return Result;
        }

        DFS(0, State, Result);
        return Result;
    }
};

四.體會

和普通的N皇後問題一樣。