程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode_N-Queens II

LeetCode_N-Queens II

編輯:C++入門知識

LeetCode_N-Queens II


一.題目

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皇後問題一樣。


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved