Pythonで右下隅に到達するために必要なセルの最小数を見つけるためのプログラム

迷路を表す2Dグリッドがあり、0は空きスペース、1は壁であるとします。 grid [0、0]から始めます。グリッドの右下隅に到達するために必要な、最小の正方形の数を見つける必要があります。到達できない場合は、-1を返します。

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

その場合、出力は5になります

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

• R：=グリッドの行数、C：=グリッドの列数

• q：=[0、0、1] A [0、0]が1の場合、それ以外の場合は新しいリスト

• A [0、0]：=1

• qの各（r、c、d）に対して、実行

  • （r、c）が（R − 1、C − 1）と同じ場合、

    • dを返す

  • 
    

    • [（r + 1、c）、（r − 1、c）、（r、c + 1）、（r、c − 1）]の（x、y）ごとに、実行

      • xが0からRの範囲にあり、yが0からCの範囲にあり、A [x、y]が0と同じである場合、

        • A [x、y]：=1

        • qの最後に（x、y、d + 1）を挿入します

• -1を返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      q = [(0, 0, 1)] if not A[0][0] else []
      A[0][0] = 1
      for r, c, d in q:
         if (r, c) == (R − 1, C − 1):
            return d
         for x, y in [(r + 1, c), (r − 1, c), (r, c + 1), (r, c −1)]:
            if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
               A[x][y] = 1
               q.append((x, y, d + 1))
      return −1
ob = Solution()
grid = [
   [0, 0, 0],
   [1, 0, 0],
   [1, 0, 0]
]
print(ob.solve(grid))

入力

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]

出力

5