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)で求められるようにすれば、全体の計算量はダイクストラの計算量だけになる。