最近、暇があれば(なくても時間を無理やり搾り出して)プログラムを書いてるので、ブログの更新はあまりやっていない。というのは寂しいと言われそうなので、プログラムの正解にヒントなるものを適当に書いておく。

online-judge.uva.es での順位は現時点315位だが、4月までに100位以内に食い込むのは当面の目標。1位になることは不可能かもしれないが、できれば今年中に上位10位内に入りたい。

問題 208 Firetruck

消防所から火事箇所までの通るルート(道筋)をすべて列挙する問題。道路の各交差点に番号が振られていて、消防所最寄の交差点は常に番号1と決められている。火事箇所は各ケースの1行に与えられている。各交差点は最大1回 しか通ってはいけないのが条件。

まともな問題だが、特殊ケースは2つ。
 1.番号1が火事箇所であるケース。ルートは1本しかない。
 2.火事箇所に通じる道筋のないケース。ルートはない。つまり、0本になる。

再帰によるバックトラッキング手法を使うが、10秒以内に実行を終わらせるには、検索範囲を絞り込む必要がある。

個人的に考えたのは、火事箇所の回りの交差点リストをつくり、これらの交差点をすべて通ったルートなら、それ以上の検索を打ち切る方法。

例えば、ケース1では、火事箇所の6に直結の交差点は4と5、の2つだけ。したがって、4と5を通ったルートはすぐ6に来るか、打ち切られるかのどちらかにする。

Comments are closed.

Post Navigation