Pythonで迷路行列をエスケープするための最小移動数

バイナリ行列があるとします。ここで、0は空のセルを表し、1は壁を表します。左上隅（0、0）から開始する場合、右下隅に到達するために必要なセルの最小数を見つける必要があります（R-1、C-1）。ここで、Rは行数、Cは数です。列の。答えが見つからない場合は、-1を返します。

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

-

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

• R：=行数
• C：=列数
• q：=空のリスト、matrix [0、0]が0の場合、最初に（0、0、1）を挿入します
• matrix [0、0]：=1
• qの各トリプレット（r、c、d）について、
  • （r、c）が（R-1、C-1）と同じ場合、
    • return d
  • [（r + 1、c）、（r --1、c）、（r、c + 1）、（r、c -1）]のx、yごとに、do
    • 0 <=x
    • matrix [x、y]：=1
    • qの最後にトリプレット（x、y、d + 1）を挿入します

例

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

def solve(matrix):
   R, C = len(matrix), len(matrix[0])
   q = [(0, 0, 1)] if not matrix[0][0] else []
   matrix[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 matrix[x][y] == 0:
            matrix[x][y] = 1
            q.append((x, y, d + 1))
   return -1

matrix = [
   [0, 0, 0, 1, 0],
   [0, 0, 1, 1, 0],
   [0, 0, 0, 1, 1],
   [1, 1, 0, 0, 0]
]
print(solve(matrix))

入力

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

出力

8