資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢在任何單元格中與所有人會面的最小步數
假設我們有一個二維矩陣，其中包含以下值：0 代表空單元格；1 代表牆壁；2 代表一個人。現在，一個人可以在一個時間單位內向上、下、左、右四個方向移動，或者留在原地。我們必須找到一個可行走單元格，使得它最大限度地減少每個人相遇所需的時間，並返回該時間。我們必須記住，兩個人可以穿過同一個空單元格，並且您可以假設任何兩個人之間總存在某種路徑。
因此，如果輸入如下所示：
| 2 | 0 | 1 | 0 |
| 1 | 0 | 0 | 2 |
| 2 | 0 | 2 | 0 |
則輸出將為 2，因為所有人最多可以在矩陣[1, 1] 位置會面，需要最多 2 步。
為了解決這個問題，我們將遵循以下步驟：
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 bfs()。這將接收 r, c
queue := 定義一個佇列，並將一個 (r, c) 對插入其中
dist := 一個鍵值對對映 {(r, c) : 0}
對於佇列中的每個 (r, c) 對，執行以下操作：
如果 dist[r, c] > 15 非零，則
退出迴圈
對於 (r, c) 的每個鄰居 (nr, nc)，執行以下操作：
如果 (nr, nc) 不在 dist 中，則
dist[nr, nc] := dist[r, c] + 1
將 (nr, nc) 插入佇列的末尾
返回 dist
從主方法執行以下操作：
dist := null
對於 A 的每個行號 r 和對應的行元素，執行以下操作：
對於每個列號 c 和行[c] 值 val，執行以下操作：
如果 val 等於 2，則
ndist := bfs(r, c)
如果 dist 為 null，則
dist := ndist
否則，
對於 dist 的每個鍵，執行以下操作：
如果鍵在 ndist 中，則
dist[key] := dist[key] 和 ndist[key] 的最大值
否則，
移除 dist[key]
如果 dist 不為空，則返回 dist 中所有值的最小值；否則返回 0
示例
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
def get_neighbor(r, c):
for nr, nc in ((r − 1, c), (r, c − 1), (r + 1, c), (r, c + 1)):
if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
yield nr, nc
def bfs(r, c):
queue = [(r, c)]
dist = {(r, c): 0}
for r, c in queue:
if dist[r, c] > 15:
break
for nr, nc in get_neighbor(r, c):
if (nr, nc) not in dist:
dist[nr, nc] = dist[r, c] + 1
queue.append((nr, nc))
return dist
dist = None
for r, row in enumerate(A):
for c, val in enumerate(row):
if val == 2:
ndist = bfs(r, c)
if dist is None:
dist = ndist
else:
for key in list(dist.keys()):
if key in ndist:
dist[key] = max(dist[key],ndist[key])
else:
del dist[key]
return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 0, 2],
[2, 0, 2, 0]
]
print(ob.solve(matrix))輸入
[ [2, 0, 1, 0], [1, 0, 0, 2], [2, 0, 2, 0] ]
輸出
2
瀏覽量：117
