C++でマトリックスの右下セルに到達するための最小ステップ数を求める方法

問題の概要

正の整数で構成された2次元マトリックス（行列）が与えられたとします。このとき、左上のセル (0, 0) から右下のセル (n-1, n-1) まで移動するために必要な最小ステップ数を求めるのが目的です。

移動のルールは以下のとおりです。現在いるセルを (i, j) とすると、次のいずれかのセルに移動できます。

• (i, j + mat[i][j]) … 現在のセルの値の分だけ右へ移動
• (i + mat[i][j], j) … 現在のセルの値の分だけ下へ移動

ただし、マトリックスの範囲を超えて移動することはできません。

入力例

例として、次のようなマトリックスを考えてみましょう。

この場合の出力は 2 となります。最短経路は以下のようになります。

(0, 0) → (0, 2) → (2, 2)

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

この問題は動的計画法（Dynamic Programming）を使うことで効率的に解くことができます。

現在いるセルを (i, j)、目標のセルを (n-1, n-1) としたとき、次のような漸化式が成り立ちます。

DP[i, j] = 1 + min(DP[i + arr[i][j], j], DP[i, j + arr[i][j]])

つまり、「そのセルからゴールまでの最小ステップ数」は、「ジャンプ先の2つのセルのうち小さい方の値 + 1（現在の移動分）」で表されます。すでに計算済みのセルの結果はメモ化しておくことで、同じ計算を繰り返さずに済みます。

C++での実装例

#include<iostream>
#define N 3
using namespace std;
int table[N][N];
bool temp_val[N][N];
int countSteps(int i, int j, int arr[][N]) {
    if (i == N - 1 and j == N - 1)
        return 0;
    if (i > N - 1 || j > N - 1)
        return INT_MAX;
    if (temp_val[i][j])
        return table[i][j];
    temp_val[i][j] = true;
    table[i][j] = 1 + min(countSteps(i + arr[i][j], j, arr), countSteps(i, j + arr[i][j], arr));
    return table[i][j];
}
int main() {
    int arr[N][N] = { { 2, 1, 2 }, { 1, 1, 1 }, { 1, 1, 1 } };
    int ans = countSteps(0, 0, arr);
    if (ans >= INT_MAX)
        cout << -1;
    else
        cout << "Number of steps: " << ans;
}

実行結果

Number of steps: 2

コードのポイント

• table[][]：各セルからゴールまでの最小ステップ数を保存するメモ化テーブルです。
• temp_val[][]：そのセルがすでに計算済みかどうかを記録するフラグ配列です。再計算を防ぎ、計算量を大幅に削減します。
• 境界チェック：マトリックスの範囲外に出た場合は INT_MAX を返し、到達不可能であることを示します。最終的に結果が INT_MAX 以上であれば、ゴールに到達できないため -1 を出力します。

このように、再帰とメモ化を組み合わせた動的計画法を用いることで、全経路を総当たりするよりもはるかに効率的に最小ステップ数を求めることができます。