Pythonの任意のセルですべての人に会うために必要な最小ステップ数を見つけるためのプログラム

これらの値が存在する2D行列があるとします。0は空のセルを表します。 1は壁を表します。 2は人を表します。これで、人は上、下、左、右の4つの方向のいずれかを歩くことができます。それ以外の場合は、1つの時間単位にとどまります。誰もが会って時間を返すのにかかる時間を最小限に抑えるように、歩きやすいセルを見つける必要があります。 2人が同じ空のセルを通り抜けることができ、2人の間には常に何らかの経路があると想定できることを覚えておく必要があります。

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

その場合、出力は2になります。これは、すべてが最大2ステップで位置行列[1、1]で出会うことができるためです。

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

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

• 関数bfs（）を定義します。これにはr、cが必要です

• queue：=キューを定義し、それにペア（r、c）を挿入します

• dist：=キーと値のペアを持つマップ{（r、c）：0}

• キュー内の各ペア（r、c）について、実行します

  • dist [r、c]> 15がゼロ以外の場合、

    • ループから出てきます

  • （r、c）の各ネイバー（nr、nc）に対して、実行

    • （nr、nc）がdistにない場合、

      • dist [nr、nc]：=dist [r、c] + 1

      • キューの最後に（nr、nc）を挿入します

  • 戻り距離

• メインの方法から、次のようにします-

• dist：=null

• 各行番号rおよびAの対応する行要素について、実行します

  • 各列番号cとrow[c]valの値について、実行

    • valが2と同じ場合、

      • ndist：=bfs（r、c）

      • distがnullの場合、

        • dist：=ndist

      • それ以外の場合

        • distのキーの各キーについて、実行します

          • キーがndistにある場合、

            • dist [key]：=最大のdist [key]、ndist [key]

          • それ以外の場合

            • dist [key]

              を削除します

• distが空でない場合は、distのすべての値の最小値を返します。それ以外の場合は、0を返します

  。

例

class Solution:
def solve(self, A):
   R, C = len(A), len(A[0])
   def get_neighbor(r, c):
      for nr, nc in ((r − 1, c), (r, c − 1), (r + 1, c), (r, c + 1)):
         if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
            yield nr, nc
      def bfs(r, c):
         queue = [(r, c)]
         dist = {(r, c): 0}
         for r, c in queue:
            if dist[r, c] > 15:
               break
            for nr, nc in get_neighbor(r, c):
               if (nr, nc) not in dist:
                  dist[nr, nc] = dist[r, c] + 1
                  queue.append((nr, nc))
         return dist
      dist = None
      for r, row in enumerate(A):
         for c, val in enumerate(row):
            if val == 2:
               ndist = bfs(r, c)
               if dist is None:
                  dist = ndist
               else:
                  for key in list(dist.keys()):
                     if key in ndist:
                        dist[key] = max(dist[key],ndist[key])
                     else:
                        del dist[key]
      return min(dist.values()) if dist else 0
ob = Solution()
matrix = [
   [2, 0, 1, 0],
   [1, 0, 0, 2],
   [2, 0, 2, 0]
]
print(ob.solve(matrix))

入力

[
   [2, 0, 1, 0],
   [1, 0, 0, 2],
   [2, 0, 2, 0] 
]

出力

2