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

leetcode筆記:N

編輯:關於C++

一. 題目描述

Follow up for N-Queens problem.

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

二. 題目分析

題目與N-Queens的方法基本相同,但比後者更為簡單,因為題目只要求輸出合適解的個數,不需要打印所有解,代碼要比上一題簡化很多。設一個全局變量,每遍歷到底部一次就增1。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution
{
public:
    int totalNQueens(int n)
    {
        this->row = vector(n, 0); // 行信息
        this->col = vector(n, 0); // 列信息
        result = 0;
        dfs(0, n, result); // 深搜
        return result;
    }

private:
    int result; // 存放打印的結果
    vector row; // 記錄每一行哪個下標是Q
    vector col; // 記錄每一列是否已有Q

    void dfs(int r, int n, int & result) // 遍歷第r行,棋盤總共有n行
    {
        if (r == n) // 可遍歷到棋盤底部,計數器加1
            ++result;

        int i, j;
        for (i = 0; i < n; ++i)
        {
            if (col[i] == 0)
            {

                for (j = 0; j < r; ++j)
                    if (abs(r - j) == abs(row[j] - i))
                        break;

                if (j == r)
                {
                    col[i] = 1; // 標記第i列,已存在Q
                    row[j] = i; // 第j行的第i個元素放入Q
                    dfs(r + 1, n, result); // 遍歷第r + 1行
                    col[i] = 0;
                    row[j] = 0;
                }

            }
        }
    }
};

四. 小結

N-Queens的後續題目N-Queens II,比前一題簡化許多,因為只要求輸出解的個數,不需要輸出所有解的具體狀況。

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