STAGE12 枝分かれ of 枝分かれ

想定解法

• 使用ブロック数 : 8
• クリア時残り体力 : 195

ステージの狙い

シンプルに難しいステージかなーと思います。
このステージが解けたとしたら上側か下側の宝箱から順に取っていくことになると思います。
この時のキャラクターの動きが「深さ優先探索」というアルゴリズムで探索する時の動きと同じになります。ステージを簡略化した図で「深さ優先探索」の動きを表すと以下のようになります。

深さ優先探索の具体的な実装方法はここでは紹介しませんが、再帰関数で実装するのが簡単です。今回はブロックを組み立てるというゲームなので、このアルゴリズムを再現するのが困難だったのでこのような解法になっています。

なお、今回の想定解法の擬似コードは

while true:
    while 前が道:
        前に1マス動く
        if 右が道:
            右を向く
    左を向く

となります。