bobuhiro11's diary

ABC 170 F- Pond Skater

23 Jun 2020

提出したコード

解いた後の振り返りが大事だと思う。

2次元平面上で、スタート位置からゴール位置までの最短経路を求める。 ただし、平面上にはいくつかブロックがあり、そのセルは通れない。 さらに、一回の移動で、同一方向に$1 … K$の任意の個数のセルを進めることができる。

頂点は$(y, x, dir)$として、グラフを考えて、ダイクストラ法で最短経路を算出すればよい。 頂点$(y, x, dir)$からの遷移は以下の通り。 移動にかかるコストを$K$倍して考えるとよい。

計算量は$O(HW log(HW))$かな。


< Educational DP Contest ABC 171 F - Strivore >