資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢島嶼之間最短橋的距離
假設我們有一個二進位制矩陣，其中 0 代表水，1 代表陸地。一個島嶼是一組在 4 個方向上連線的 1。島嶼要麼被 0（水）包圍，要麼被邊緣包圍。我們必須找到連線兩個島嶼的最短橋的長度。
所以，如果輸入是這樣的
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
那麼輸出將是 1。這將連線 (1,0) 到 (1,2) 點。
為了解決這個問題，我們將遵循以下步驟：
row := 矩陣的行數
col := 矩陣的列數
定義一個函式 dfs()。它將接收 i、j、s 作為引數
如果 (i, j) 在 s 中，則
返回
如果 mat[i, j] 等於 0，則
返回
將 (i, j) 插入 s
如果 i - 1 >= 0，則
dfs(i - 1, j, s)
如果 i + 1 < row，則
dfs(i + 1, j, s)
如果 j - 1 >= 0，則
dfs(i, j - 1, s)
如果 j + 1 < col，則
dfs(i, j + 1, s)
從主方法執行以下操作：
seen := 一個新的集合
對於 i 從 0 到 row 的範圍，執行
如果 seen 的大小 > 0，則
退出迴圈
對於 j 從 0 到 col 的範圍，執行
如果 mat[i, j] 等於 1，則
dfs(i, j, seen)
退出迴圈
q := 一個雙端佇列
對於 seen 中的每個陸地，執行
(i, j) := 陸地
如果 i - 1 >= 0 且 mat[i - 1, j] 等於 0，則
將 (i - 1, j, 1) 插入 q 的末尾
如果 i + 1 < row 且 mat[i + 1, j] 等於 0，則
將 (i + 1, j, 1) 插入 q 的末尾
如果 j - 1 >= 0 且 mat[i, j - 1] 等於 0，則
將 (i, j - 1, 1) 插入 q 的末尾
如果 j + 1 < col 且 mat[i, j + 1] 等於 0，則
將 (i, j + 1, 1) 插入 q 的末尾
當 q 的大小 > 0 時，執行
(i, j, dist) := q 的左邊的項，並從 q 的左邊刪除該項
如果 (i, j) 在 seen 中，則
進入下一次迭代
將 (i, j) 標記為 seen
如果 mat[i, j] 等於 1，則
返回 dist - 1
如果 i - 1 >= 0，則
將 (i - 1, j, dist + 1) 插入 q 的末尾
如果 i + 1 < row 不為零，則
將 (i + 1, j, dist + 1) 插入 q 的末尾
如果 j - 1 >= 0，則
將 (i, j - 1, dist + 1) 插入 q 的末尾
如果 j + 1 < col 不為零，則
將 (i, j + 1, dist + 1) 插入 q 的末尾
示例
讓我們看看以下實現以獲得更好的理解：
import collections class Solution: def solve(self, mat): row = len(mat) col = len(mat[0]) def dfs(i, j, s): if (i, j) in s: return if mat[i][j] == 0: return s.add((i, j)) if i - 1 >= 0: dfs(i - 1, j, s) if i + 1 < row: dfs(i + 1, j, s) if j - 1 >= 0: dfs(i, j - 1, s) if j + 1 < col: dfs(i, j + 1, s) seen = set() for i in range(row): if len(seen) > 0: break for j in range(col): if mat[i][j] == 1: dfs(i, j, seen) break q = collections.deque() for land in seen: i, j = land if i - 1 >= 0 and mat[i - 1][j] == 0: q.append((i - 1, j, 1)) if i + 1 < row and mat[i + 1][j] == 0: q.append((i + 1, j, 1)) if j - 1 >= 0 and mat[i][j - 1] == 0: q.append((i, j - 1, 1)) if j + 1 < col and mat[i][j + 1] == 0: q.append((i, j + 1, 1)) while len(q) > 0: i, j, dist = q.popleft() if (i, j) in seen: continue seen.add((i, j)) if mat[i][j] == 1: return dist - 1 if i - 1 >= 0: q.append((i - 1, j, dist + 1)) if i + 1 < row: q.append((i + 1, j, dist + 1)) if j - 1 >= 0: q.append((i, j - 1, dist + 1)) if j + 1 < col: q.append((i, j + 1, dist + 1)) ob = Solution() matrix = [ [0, 0, 1], [1, 0, 1], [1, 0, 0], ] print(ob.solve(matrix))
輸入
[ [0, 0, 1], [1, 0, 1], [1, 0, 0], ]
輸出
1
396 次瀏覽
