用 Python 编写程序，查找与所有人见面所需覆盖的最小距离
假设我们有一个 2D 矩阵，其中有几个值，如下所示 −
0 表示一个空单元格。
1 表示一堵墙。
2 表示一个人。
在这里，一个人可以朝这四个方向(上、下、左、右)中的任何一个方向行走。我们必须找到一个不是墙壁的单元格，以使每个人步行的总行程距离最小化，并最终找到距离。
因此，如果输入如下
| 2 | 0 | 1 | 0 |
| 1 | 0 | 1 | 2 |
| 0 | 0 | 2 |
那么输出将是 7，因为最佳交汇点是右下角。
为了解决这个问题，我们将遵循以下步骤 −
twos := a new map,costs := 一个新的映射
对于矩阵中的每个索引 i 和行 r，执行
对于 r 中的每个索引 j 和值 v，执行
如果 v 与 2 相同，则
twos[i, j] := [i, j, 0]
costs[i, j] := 制作一个大小与给定矩阵相同的 2D 矩阵并用无穷大填充
对于 twos 中的每个键值对 (k, q)，执行
seen := 一个新的集合
当 q 不是时空，执行
(i, j, cost) := 从 q 中删除第一个元素
如果 (i, j) 在 seen 中，则
进行下一次迭代
将(i, j) 添加到 seen 中
costs[k, i, j] := cost
对于 ((1, 0), (−1, 0), (0, 1), (0, −1)) 中的每个 (di, dj)，执行
(ni, nj) := (i + di, j + dj)
如果 ni 和 nj 在矩阵范围内，并且matrix[ni, nj] 不为 1，则
在 q 末尾插入 (ni, nj, cost + 1)
ans := infinity
对于范围从 0 到矩阵行数的 i，执行
对于范围从 0 到矩阵列数的 j，执行
cur_cost := 0
对于所有成本值列表中的每个 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
