假设我们有一个2D矩阵，那么下面的值很少-
0表示一个空单元格。
1代表墙。
2代表一个人。
在这里，一个人可以走这四个方向（上，下，左和右）中的任何一个。我们必须找到一个不是墙的牢房，以使每个人必须走到的总旅行距离最小化，并最终找到该距离。
所以，如果输入像
| 2 | 0 | 1 | 0 |
| 1 | 0 | 1 | 2 |
| 0 | 0 | 2 | 2 |
那么输出将是7，因为最佳的交汇点是右下角。
为了解决这个问题，我们将遵循以下步骤-
二进制：=新映射，成本：=新映射
对于矩阵中的每个索引i和行r，
如果v与2相同，则
twos [i，j]：= [i，j，0]
cost [i，j]：=制作一个二维矩阵，其大小为给定矩阵，并用无穷大填充
对于每个索引j和r中的值v，执行
对于二的每个键值对(k,q)，请执行
(i,j,cost)：=从q中删除第一个元素
如果看到(i,j)，则
加(i,j)到看到
成本[k，i，j]：=成本
对于（(1,0)，(-1,0)，(0,1)，(0,-1)）中的每个(di,dj)
进行下一次迭代
在q的末尾插入（ni，nj，cost + 1）
(ni,nj)：=（i + di，j + dj）
如果ni和nj在矩阵范围内，并且matrix [ni，nj]不为1，则
看过：=一套新的
当q不为空时，执行
ans：=无限
对于范围在0到矩阵行数的i，执行
cur_cost：= 0
对于所有成本值列表中的每个arr，
ans：= ans和cur_cost的最小值
cur_cost：= cur_cost + arr [i，j]
对于范围从0到矩阵的列数的j，执行
返回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