数据结构
网络
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 次查看
