Mujin Programming Challenge 2018 E. 迷路

問題

N*Mのマス目があり、各マスには障害物がある場合がある。
時刻0にスタート地点からスタートし、できるだけ短い時間でゴール地点に移動したい。

各時刻では、「1秒かけて隣接マスに移動する」か、「移動せずにマスに待機する」ことができる。
しかし、各時刻で移動できる方向が1方向にのみ限られており、どの方向に移動できるかは文字列Dで与えられ、時刻tの場合はt mod |D|番目の文字が移動できる方向を示す。

ゴールまでの最短時間を求めよ。

制約

• 2 <= N, M <= 1000
• 1 <= |D| <= 100000

解法

ある地点にいる場合、方向Aの隣接マスに移動するためには、「ぐるっと回って移動する」か、「その場で待つ」ことができる。

その場で待つ場合、移動したい方向の文字になるまで待つ必要がある。
この待ち時間をwait(t, angle)で求められたとすると、結局、「その地点にたどり着く最短時間」がわかっている場合、隣接マスへの移動は「その最短時間＋wait(t, angle) + 1」(最後の+1は移動時間)で移動できるので、これでダイクストラすればよい。

wait(t, angle)は単純に計算するとO(|D|)かかってしまうが、前処理として、Dを2つつなげた文字列を後ろからなめて待ち時間をO(1)で求められるようにすれば、全体の計算量はダイクストラの計算量だけになる。