King’s Ring Tower（Maximum-Cup 2013 [G]）

概要

問題文 → ■
公式解説 → なさそう
自分の提出 → ■

読解に極振りした問題ですね。実装は意外と簡単なので、頑張ってください。

問題概要

$3$ 次元グリッドがある。マスには以下の種類がある。

• 草原、街、階段、指輪、現在地：コスト $1$ でこれらへの移動可能
• レベル $x$ の敵：自分のレベル $\text{lv}$ が $x$ 以上のときに、コスト $x+1$ で移動可能。自分のレベルと同じならば、レベルアップ。
• 壁、空：移動不可能

これに加えて、階段の上り下りが可能。

---

意外と要素は少ないです。「草原と街は完全に同一」「壁と空は完全に同一」などに注意しましょう。

階段 $(t,h,w)$ からの移動先は、$(t\pm 1,h,w)$ ではありません。上下の階の階段の対応する階段の位置です。これは前計算で求めておきましょう。

---

「今の地震の影響で現在いる階から下の階に下りられなくなっている」ことに注意しましょう。「現在いる階」が、ひとつめの MAP とは限りません。

解法

$(t,h,w,lv)$ を状態として Dijkstra 法をすればよいです。

移動コストが $100$ 以下であることを利用して、Dial’s Algorithm に置き換えることもできます。