Pythonですべての人に会うためにカバーする必要がある最小距離を見つけるためのプログラム

2D行列があるとすると、以下のような値はほとんどありません-

• 0は空のセルを表します。

• 1は壁を表します。

• 2は人を表します。

ここでは、人はこれらの4つの方向（上、下、左、右）のいずれかを歩くことができます。壁ではないセルを見つけて、各人が歩いて行かなければならない総移動距離を最小にし、最終的に距離を見つける必要があります。

したがって、入力が次のような場合

最適なミーティングポイントは右下隅であるため、出力は7になります。

これを解決するには、次の手順に従います-

• twos：=新しいマップ、コスト：=新しいマップ

• 行列の各インデックスiと行rについて、次のようにします

  • rの各インデックスjと値vについて、実行します

    • vが2と同じ場合、

      • twos [i、j]：=[i、j、0]

      • cost [i、j]：=与えられた行列と同じサイズの2D行列を作成し、無限大で埋める

• 2つのキーと値のペア（k、q）ごとに、実行します

  • 見た：=新しいセット

  • qが空でない間、実行します

    • （i、j、コスト）：=qから最初の要素を削除

    • （i、j）が表示されている場合、

      • 次のイテレーションに行く

    • add（i、j）をseenに追加

    • コスト[k、i、j]：=コスト

    • （（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：=無限大

• 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