Pythonで迷路の右下隅に到達するまでの最小マス数を求めるプログラム

0が空きマス、1が壁を表す2次元グリッド（迷路）があるとします。左上の grid[0][0] からスタートし、グリッドの右下隅に到達するまでに通過する必要のあるマスの最小数を求めます。もし右下隅に到達できない場合は −1 を返します。

例えば、入力が以下のような場合を考えてみましょう。

この場合、出力は 5 となります。

解法のアプローチ：幅優先探索（BFS）

この問題は幅優先探索（BFS）を使うことで効率的に解けます。BFSは最短経路を求めるのに適したアルゴリズムで、各セルに到達した時点での移動回数を記録しながら探索を進めます。具体的な手順は以下の通りです。

• R := グリッドの行数、C := グリッドの列数とします。

• A[0][0] が 1（壁）の場合は空のキューを用意し、そうでなければ q := [(0, 0, 1)] で初期化します。第3要素の「1」はスタート地点自体も1マスとしてカウントすることを意味します。

• A[0][0] := 1 とし、スタート地点を訪問済みとしてマークします。

• キュー内の各 (r, c, d) について以下を繰り返します。

  • (r, c) が (R−1, C−1)、つまり右下隅と一致した場合は d を返します。

  • そうでなければ、隣接する4方向 [(r+1, c), (r−1, c), (r, c+1), (r, c−1)] のそれぞれについて、(x, y) がグリッドの範囲内（0 ≤ x < R かつ 0 ≤ y < C）であり、かつ A[x][y] が 0（未訪問の空きマス）である場合：

    • A[x][y] := 1 として訪問済みにします。

    • (x, y, d + 1) をキューの末尾に追加します。

• キューが空になっても右下隅に到達できなかった場合は −1 を返します。

ポイントは、訪問済みのセルを壁と同じように扱うことで再訪問を防ぎ、無限ループを回避している点です。これにより各セルは最大1回しか処理されず、計算量は O(R×C) に抑えられます。

それでは、実際の実装を見て理解を深めましょう。

実装例

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