前回の続き
状態遷移のコーディング 宣教師と人食い人種
ソースは前回のリンクの最後に追加してあります
前回はランダムで解くもので
今回は最短を検索してみます。
アルゴリズムは迷路の探索の亜種です。
船に乗れる人のパターンが5つとはたと気がついて、これはグルグルまわせばできるタイプかと実装してみました。
簡単な説明
spに検索点を入れていきます。情報としては岸1、岸２の人 船の位置 さらに最後解答するためにこれまでの歴史を入れます
out 岸1、岸２の人 船の位置の組み合わせで検索点に入ったものが入ります 前に検索していたら再度検索しないためです
answer 岸２に全ての人移って、その回数がこれまでの中で最短なら歴史が移されます。
11 検索点があればループします
12 検索点からひとつ取り出します（検索点はひとつなくなります）
13 船に乗る5パターンでループします
14-24 渡せるようなら渡します
25 人食いが宣教師を食べてないか判定します あと最短でない時も対象外です
26 すでに検索点であれば次のパターンへ
27 検査済みに現在の検索点を追加します
28 歴史に追加です
29 新しく検索点を追加します
30-32 渡りきっていて、歴史が最短なら答えを塗り替えます
33 最短の答えを表示します
実は設計ミスっぽい箇所があるのですが結果オーライでなんとか動いています。
16 21 行で条件外ならcontinueが必要なのですが以下のチェックで弾かれているようです。
よくあることです。
なぞの技
18 23 landは常にmからs順に並べてかえています。それによって船に乗れるか判定を簡略化しています。
28 桁揃えのためにスペースを追加して文字列の長さでスライスしています。
終わりに
一般的には難しいかもしれません。
私の場合は似たパターンを100回ぐらいは作ってそうなので染み付いてしまってます。
TVerでシグナルのスペシャルドラマを見ながら完成しています。
