資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法學研究Python程式：檢查棋盤是否為有效的N皇后解
假設我們有一個n x n矩陣代表一個棋盤。其中一些元素為1，一些元素為0，其中1代表皇后，0代表空單元格。我們必須檢查該棋盤是否為N皇后問題的有效解。眾所周知，如果棋盤上任意兩個皇后都不能互相攻擊，則該棋盤為有效的N皇后解。
因此，如果輸入如下所示：
則輸出為True
為了解決這個問題，我們將遵循以下步驟：
- n := 矩陣的行數
- rows := 一個新的集合，cols := 一個新的集合，diags := 一個新的集合，rev_diags := 一個新的集合
- 對於範圍0到n內的i：
- 對於範圍0到n內的j：
- 如果matrix[i, j]為1，則：
- 將i插入rows
- 將j插入cols
- 將(i - j)插入diags
- 將(i + j)插入rev_diags
- 如果matrix[i, j]為1，則：
- 對於範圍0到n內的j：
- 如果rows的大小、cols的大小、diags的大小和rev_diags的大小都等於n，則返回true，否則返回false。
讓我們來看下面的實現，以便更好地理解。
示例
class Solution: def solve(self, matrix): n = len(matrix) rows = set() cols = set() diags = set() rev_diags = set() for i in range(n): for j in range(n): if matrix[i][j]: rows.add(i) cols.add(j) diags.add(i - j) rev_diags.add(i + j) return len(rows) == len(cols) == len(diags) == len(rev_diags) == n ob = Solution() matrix = [ [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0] ] print(ob.solve(matrix))
輸入
matrix = [ [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0] ]
輸出
True
更新於：2020年11月26日
749 次瀏覽
廣告