程序以找到满足Python中所有人所需的最小距离

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个2D矩阵，那么下面的值很少-

  • 0表示一个空单元格。

  • 1代表墙。

  • 2代表一个人。

在这里，一个人可以走这四个方向（上，下，左和右）中的任何一个。我们必须找到一个不是墙的牢房，以使每个人必须走到的总旅行距离最小化，并最终找到该距离。

所以，如果输入像

2010
1012
0022

那么输出将是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

        以上是 程序以找到满足Python中所有人所需的最小距离 的全部内容， 来源链接： utcz.com/z/316525.html

        回到顶部