ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2899 - 遭難

問題
提出コード
夏休みの宿題です。
この問題は、会津合宿で既読だけつけていたので、そのときにちらっと解説を聞いてしまっています。
くコ:彡

解法

解き方は2パターンあり、どちらも右手法を使用します。簡単に説明すると、迷路などで、右手を壁に当て続けて歩くと、必ずスタートからゴールへ行ける(もしくはスタートへ戻る)というものです。今回のようなパターンだと、必ず一周して同じ地点に戻ってくることができます。
f:id:emtubasa:20181017215726p:plain
真ん中の丸がスタート地点だとすると、矢印のように進んでいくイメージです。
基本的にはこれを利用して島の形状を把握していきます。2パターンある解き方とは、

  • 右手法を利用して、島の形状を記憶し、問題で与えられた島の中から、一致する形を探してスタート地点を逆算する

  • 陸地の部分全てにAORイカちゃんを立てて、全員同時に同じ方向に進み、クエリと一致しなくなったものから消去していく

になります。今回は、実装がぱっと思いついた後者のパターンを利用しました。

まず初めに、陸地の座標をすべて記録しておきます(最後に使用します)。その後、右手法を開始します。まずは、壁に右手を当てる必要があるので、4方向のうち好きな方向に、進めなくなるまで直進します。
そうしたら、いよいよ壁をつたって進んでいきます。次に進む方向をxとします。方向は0~3の4パターンで、数が増えると90度左に向くとします。
まずは、x方向に進むことができるかどうかを調べます。
進めない(前が海である)場合は、左を向きます。つまり、xに1を追加します。その後、同じことをします。
進めた場合は、クエリによって自動的にそのマスに進みます。
右手法は、常に右側に壁がある状態で進まなければなりません。1マス進んだあと、右側に壁がある保証はどこにもないので、次に進む方向を右向き、つまりx-1としておきます。

...
.##
.#.

現在一番下の行の、陸地のマスで上を向いているとします。上に進むことができるので上に進むのですが、その次は右に進むことができます。ここで、右向きにする操作を怠ると、右側のマスに行くことができなくなってしまいます。ということで、

  • 今向いている方向に進むことができたら、進んでからいったん右を向く

  • 今向いている方向に進むことができなかったら、左を向く

という操作を行っていけば、島の外周をすべてまわることができます。
最後に座標の特定です。
現在、上下に何マス、左右に何マス進んだか、という情報をどこかに記録しておきます。
すると、次にクエリによって進んだときに、初期状態からどれだけ進んだか、というのが即座にわかります。
一番最初に行った、全ての陸地の座標の記録それぞれに、累計で進んだ距離を足し合わせてあげると、現在の移動先の座標がわかります。
その移動先の座標が、

  • 今のクエリで進むことができたなら陸地

  • 進むことができなかったら海

である必要があるので、この条件と辻褄が合うかどうかチェックします。合わなかった場合、初期の座標の候補から消えるので、その座標の情報を捨てます。
こうしていって、最終的に残った1つの座標が、本物のAORイカちゃんが最初にいた座標になります。