資料結構
網路
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 | 1 | 2 |
| 0 | 0 | 2 | 2 |
則輸出將為 7，因為最佳會合點是右下角。
為了解決這個問題，我們將遵循以下步驟：
twos := 一個新的對映，costs := 一個新的對映
對於矩陣中的每個索引 i 和行 r，執行以下操作：
對於 r 中的每個索引 j 和值 v，執行以下操作：
如果 v 等於 2，則
twos[i, j] := [i, j, 0]
costs[i, j] := 建立一個與給定矩陣大小相同的二維矩陣，並用無窮大填充。
對於 twos 中的每個鍵值對 (k, q)，執行以下操作：
seen := 一個新的集合
當 q 不為空時，執行以下操作：
(i, j, cost) := 從 q 中刪除第一個元素。
如果 (i, j) 在 seen 中，則
進入下一個迭代。
將 (i, j) 新增到 seen 中。
costs[k, i, j] := cost
對於 (di, dj) 中的每個 ((1, 0), (−1, 0), (0, 1), (0, −1))，執行以下操作：
(ni, nj) := (i + di, j + dj)
如果 ni 和 nj 在矩陣範圍內，並且 matrix[ni, nj] 不為 1，則
將 (ni, nj, cost + 1) 插入到 q 的末尾。
ans := 無窮大
對於從 0 到矩陣行數的 i，執行以下操作：
對於從 0 到矩陣列數的 j，執行以下操作：
cur_cost := 0
對於 costs 所有值的列表中的每個 arr，執行以下操作：
cur_cost := cur_cost + arr[i, j]
ans := ans 和 cur_cost 的最小值。
返回 ans。
讓我們看看以下實現，以便更好地理解：
示例
class Solution:
def solve(self, matrix):
twos = {}
costs = {}
for i, r in enumerate(matrix):
for j, v in enumerate(r):
if v == 2:
twos[(i, j)] = [(i, j, 0)]
costs[(i, j)] = [[1e9 for _ in matrix[0]] for _
in matrix]
for k, q in twos.items():
seen = set()
while q:
i, j, cost = q.pop(0)
if (i, j) in seen:
continue
seen.add((i, j))
costs[k][i][j] = cost
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ni, nj = i + di, j + dj
if (ni >= 0 and nj >= 0 and ni < len(matrix) and nj < len(matrix[0]) and matrix[ni][nj] != 1):
q.append((ni, nj, cost + 1))
ans = 1e9
for i in range(len(matrix)):
for j in range(len(matrix[0])):
cur_cost = 0
for arr in costs.values():
cur_cost += arr[i][j]
ans = min(ans, cur_cost)
return ans
ob = Solution()
matrix = [
[2, 0, 1, 0],
[1, 0, 1, 2],
[0, 0, 2, 2]
]
print(ob.solve(matrix))輸入
matrix = [ [2, 0, 1, 0], [1, 0, 1, 2], [0, 0, 2, 2]]
輸出
7
205 次檢視
