これはインタビューの質問です。「フロッガー」を再生するアルゴリズムを設計します。つまり、交通量の多い道路を渡らなければならないカエルを誘導します。かえるは前後左右に移動でき、車は左にしか動かず、かえるも車も一度に 1 か所ずつ移動します。
どうすればそれをいくつかの基本的なよく知られたアルゴリズムに減らすことができるのだろうか。ゲームに「時間」がなければ、安全な位置のグラフを作成し、カエルの目的地への道を見つけます。しかし、私はこのアプローチを使用することはできません。
「フロッガー」をよく知られた問題にするにはどうすればよいですか?
このようなものが単純な形で機能すると思います。（これは、ゲームを解決する方法ではなく、ゲームを実行する方法であると仮定します）
1) build array to store all tiles on map (each segment of road / water / log)
2) build list to store car / log locations
3) Set up a timer
4) on timer tick, update array of locations with full/empty tiles for each car / log in list (2)
5) check whether the current locaiton of the frog is in the same location as a log / car
6) repeat 4/5 while frog can move
そんな感じ？
車とカエルが慎重に、一度に 1 つの「正方形」を移動すると仮定すると、カエルが垂直に (道路を横切って) 移動した回数を V で表し、カエルが水平に (車線に沿って) 移動した回数を表しましょう。 ) by H. 5 つのレーン、1 ～ 5 の場合、カエルは T=X + 2*V + H の形式の時点でレーン X にいることができます。
時点 T での各車線の車の状態は決定論的であるため、将来の妥当な時間の道路全体の状態を生成できます: L(1,T)L(2,T). .L(5,T)。L(1,1 + 2*V + H)L(2,2 + 2*V + H)...L(5,5 + 2*V + H という形式の架空の道路状態を生成することをお勧めします。 ）、反対側に開いた直線がある状態を探して、時間要素を排除します。
実際には、ブルート フォースを使用していますが、適切な数のレーンと許可された移動を前提として、そうすべきではない理由はありません。