ABC 170 F- Pond Skater

提出したコード

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

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

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

• 方向を変えるときは、$K$で切り上げ。
  • $cost(y, x, new dir) \leftarrow ((cost(y, x, dir) + K -1) / K) * K$
• 同方向に移動。$dir$は上下左右の4種類。$dx$、$dy$は方向ごとの差分。
  • $cost(y + dy, x + dx, dir) \leftarrow cost(y, x, dir) + 1$

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