C++で解くカエルジャンプ問題｜メモ化再帰で川渡りを判定する方法

問題概要

カエルが川を渡る場面を考えてみましょう。川は x 単位ごとの区間に分かれており、各区間には石がある場合があります。カエルは石の上に着地することはできますが、水面に落ちることは許されません。ここでは、石の位置を昇順にソートしたリストが与えられ、「カエルが最後の石に着地して川を渡り切ることができるかどうか」を判定します。初期状態ではカエルは最初の石の上におり、最初のジャンプは必ず 1 単位でなければならないものとします。

ジャンプのルール

直前のジャンプが k 単位だった場合、次のジャンプは k − 1 単位、k 単位、k + 1 単位 のいずれかでなければなりません。また、カエルは前方向きにしかジャンプできないものとします。

入力例と答え

たとえば、配列が [0,1,3,4,5,7,9,10,12] のように与えられた場合、答えは true になります。カエルは 1 単位のジャンプで位置 1 の石へ、続いて 2 単位のジャンプで位置 3 の石へ、さらに 2 単位で位置 5、2 単位で位置 7、2 単位で位置 9、そして最後に 3 単位のジャンプで位置 12 の最後の石へと着地できるためです。

解法のアプローチ（メモ化再帰）

この問題は、深さ優先探索（DFS）にメモ化を組み合わせることで効率よく解くことができます。手順は以下の通りです。

• 探索済みの状態を記録するためのマップ visited を定義する
• 関数 canCross() を定義する。引数は石の配列 stones、現在位置 pos（初期値 0）、直前のジャンプ距離 k（初期値 0）
• key := pos OR（k を 11 ビット左シフト）として、位置とジャンプ距離を 1 つのキーにまとめる
• key が visited にすでに存在する場合は、visited[key] の値を返す（同じ状態の再計算を避ける）
• i := pos + 1 から始めて i が stones のサイズ未満である間、i を 1 ずつ増やしながら以下を繰り返す
  • gap := stones[i] − stones[pos]（次の石までの間隔）を求める
  • gap < k − 1 の場合は、その石には届かないため何もせず次の反復へ進む
  • gap > k + 1 の場合は、これ以降の石にも届かないため、visited[key] := false として false を返す
  • canCross(stones, i, gap) の呼び出し結果が真（非ゼロ）の場合は、visited[key] = true として true を返す
• ループを抜けたら、pos が stones のサイズ − 1（最後の石のインデックス）と一致する場合は true、そうでなければ false を visited[key] に設定する
• 最後に visited[key] を返す

ポイントは key = pos | (k << 11) というビット演算です。「現在位置」と「直前のジャンプ距離」という 2 つの情報を 1 つの整数にエンコードすることで、ハッシュマップのキーとして扱えるようにしています。また、gap > k + 1 となった時点でそれ以降の石との間隔はさらに広がるだけなので、そこで即座に探索を打ち切れるのも効率化の大きなポイントです。状態数は「位置 × ジャンプ距離」の組み合わせに抑えられるため、全体の計算量は O(N²) 程度に収まります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    unordered_map < lli, int > visited;
    bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
        lli key = pos | k << 11;
        if(visited.find(key) != visited.end())return visited[key];
        for(int i = pos + 1; i < stones.size(); i++){
            int gap = stones[i] - stones[pos];
            if(gap < k - 1)continue;
            if(gap > k + 1){
                return visited[key] = false;
            }
            if(canCross(stones, i, gap))return visited[key] = true;
        }
        return visited[key] = (pos == stones.size() - 1);
    }
};
main(){
    Solution ob;
    vector<int> v = {0,1,3,5,6,8,12,17};
    cout << (ob.canCross(v));
}

入力

0,1,3,5,6,8,12,17

出力

1

出力が 1（true）となっており、この石の配置ではカエルが最後の石まで渡り切れることを示しています。実際、1 → 2 → 2 → 3 → 4 → 5 単位というジャンプを重ねることで、すべての着地点を石の上に保ったまま対岸へ到達できます。