Pythonでグリッドの左上から右下までの移動経路数を求めるアルゴリズム

N × M の2値行列を考えます。ここで、0は空きセル（通過可能）、1はブロックされたセル（通過不可）を表します。左上の角からスタートして、右下の角に到達するまでの移動方法が何通りあるかを求めます。答えが非常に大きくなる場合は、10^9 + 7 で剰余を取ります。

例えば、入力が以下のような行列だったとします。

この場合の出力は 2 になります。右下に到達できる経路は「右 → 下 → 右 → 下」と「下 → 右 → 右 → 下」の2通りしかないためです。

解法のアプローチ：動的計画法（DP）

この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解けます。各セルに「そのセルに到達できる経路数」を記録していき、左上から順に累積させていくのがポイントです。手順は以下の通りです。

• 元の行列と同じサイズのDPテーブル dp を作成し、すべて0で初期化します。
• dp[0][0] := 1 とします（スタート地点には1通りの到達方法がある）。
• 1行目以降の最初の列について処理します。
  • matrix[i][0] が1なら、そこでループを抜けます（それより先は到達不可能）。
  • そうでなければ、dp[i][0] := 1 とします。
• 同様に、最初の行の各列についても処理します。
  • matrix[0][j] が1なら、ループを抜けます。
  • そうでなければ、dp[0][j] := 1 とします。
• 残りの全セルについて、次のようにDPテーブルを埋めていきます。
  • matrix[i][j] が1（ブロックされている）なら、dp[i][j] := 0。
  • そうでなければ、dp[i][j] := dp[i-1][j] + dp[i][j-1]（上から来る経路数 + 左から来る経路数）。
• 最後に、dp の右下の値を返します。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
    def solve(self, matrix):
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        dp[0][0] = 1
        for i in range(1, len(matrix)):
            if matrix[i][0] == 1:
                break
            else:
                dp[i][0] = 1
        for j in range(1, len(matrix[0])):
            if matrix[0][j] == 1:
                break
            else:
                dp[0][j] = 1
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[-1][-1]
ob = Solution()
matrix = [
    [0, 0, 1],
    [0, 0, 0],
    [1, 1, 0]
]
print(ob.solve(matrix))

入力

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]

出力

2

計算量について

このアルゴリズムの時間計算量は O(N × M)、空間計算量も O(N × M) です。行列のサイズに比例して処理が増えるため、大きなグリッドでも効率的に経路数を求められます。なお、経路数が大きくなる可能性がある場合は、各加算後に 10^9 + 7 の剰余を取ることでオーバーフローを防げます。