ichirin2501's diary

いっちりーん。

AOJ.1178 A Broken Door

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1178&lang=jp

 

35msまで高速化頑張ってました。

現在1位の29msに届かなかったのが残念です。

解法はいくつかあるようですが、BFS+ダイクストラで解きました。

入口から出口までの1つの経路を考えたとき、通過するドアのうちで故障していたら最も困るケース(必要になるカード枚数が一番多い)が、その経路におけるコストになります。

どのドアが故障しているかは事前にわからないので、部屋から部屋へ移動するときに、そのドアが故障していた場合のカード使用枚数を調べる必要があります。

これは、ある部屋(x,y)から方向dirのドアが故障していた場合として、出口までの最小のカード使用枚数をBFSで計算します。

それから、入口からある部屋までの経路のうちで、もしドアが故障していた場合における入口から出口までのコストで最悪のものをworststepとし、これをダイクストラにおける比較コストにします。

 

見落としとしては、ある部屋(x,y)において2つの状態を考えます。

状態i : 現在のカード使用数 = a、worststep = bとします

状態j : 現在のカード使用数 = c、worststep = dとします

このとき、worststepだけで比較を行うと間違った答えになる場合があります。

仮に b < d でも、a > c の場合、状態jのほうが後になって最適解を出す場合があります。

ですので、この場合はどちらも最適解を導く可能性があるので、両方とも状態を保持する必要があります。

 

にしても、1位速いなぁ…。