AOJ 2419 - Acrophobia
問題リンク
https://onlinejudge.u-aizu.ac.jp/problems/2419
問題概要
H*Wのマス目上を上下左右に移動します。Sからスタートし全てのMを一回以上通りながらGにたどり着くのにかかる最短時間を求めてください。隣り合うマス目の移動には1秒かかりますが穴の付近では変化します。(問題文参照)
制約
- 2 <= H,W <= 100
- 1 <= (Mの個数) <= 5
方針
まずそれぞれの関係をグラフで表してみます。便宜上Mには番号をふっておきます。
だいぶスッキリしました。
求めるものは一筆書きのようにすべてのMを巡るときのSからGへの最短時間です。
Mが最大5と小さいことに注目するとMの巡り方全通りを調べられることがわかります (next_permutationを用いると簡単)。 S → (Mの順列) → G の順で巡るときの移動時間の和をとっていき、それらの最小値をとってくれば解が求まります。
あとは各頂点間の最短移動時間を求めておけばよく、これはマス目ごとの穴の影響を考慮したコストを求めておけば各頂点を始点としたダイクストラ法で求められます。
以上でこの問題は解けました。
コメント
このようなグラフのすべての頂点をすべて一回ずつ通るようなパスのことをハミルトン路と言います。最短ハミルトン路問題はbitDPを用いればO(N22N)で解くことができます。(N<=18程度が限界)
