資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python中查詢二元矩陣中的最大路徑長度
在這個問題中，我們得到一個大小為 m X n 的方形矩陣 mat[][]，每個元素都是 0 或 1。如果一個元素的值為 1，則表示它已連線；如果值為 0，則表示它未連線。我們的任務是在二元矩陣中找到最大路徑長度。
問題描述 − 為了解決這個問題，我們需要找到矩陣上最長的路徑，這意味著矩陣中所有值為1的元素。在找到路徑之前，我們將最多將一個 0 轉換為 1。
讓我們來看一個例子來理解這個問題：
輸入
mat[][] = {{1, 0},
{0, 1}}輸出
3
解釋
We can convert 0 at index (0, 1) or (1, 0) to maximise the path length.
解決方案方法
一個簡單的解決方案是透過在將每個 0 轉換為 1 後查詢路徑長度來實現。我們將使用深度優先搜尋來查詢路徑長度，然後返回所有路徑長度中的最大值。
一個有效的解決方案是消除進行多次轉換的需要，並選擇一個能給出最有希望的解決方案的轉換。我們將找到一個組，使得將一個 0 轉換為 1 將返回最長的路徑。
程式演示了我們解決方案的工作原理：
示例
def FindNeighbor(R, C, N):
for nr, nc in (((R - 1), C), ( (R + 1) , C), (R, (C - 1) ), (R, (C + 1) )):
if 0 <= nr < N and 0 <= nc < N:
yield nr, nc
def DFSTraversal(R, C, index, mat, N):
maxLen = 1
mat[R][C] = index
for nr, nc in FindNeighbor(R, C, N):
if mat[nr][nc] == 1:
maxLen += DFSTraversal(nr, nc, index)
return maxLen
def findLargestPath(mat):
N = len(mat)
maxPath = {}
index = 2
for i in range(N):
for j in range(N):
if mat[i][j] == 1:
maxPath[index] = DFSTraversal(i, j, index, mat, N)
index += 1
maxPathLen = max(maxPath.values() or [0])
for i in range(N):
for j in range(N):
if mat[i][j] == 0:
seen = {mat[nr][nc] for nr, nc in FindNeighbor(i, j, N) if mat[nr][nc] > 1}
maxPathLen = max(maxPathLen, 1 + sum(maxPath[i] for i in seen))
return maxPathLen
I = [[1, 0], [0, 1]]
print("The length of largest path is " + str(findLargestPath(I)))輸出
The length of largest path is 3
更新於：2021年3月12日
219 次瀏覽
廣告