Description:
自機は戦車で、ターゲットの場所への移動にかかる最小ターン数を求めてください。
フィールドのサイズは、N*M(2<=N,M<=300)で、各マスは、川、レンガ、鉄壁、空白のどれか。
1ターンに出来る行動は、次の二つのうちどれか。
1. 四方向のうちの空白マスに移動
2. 四方向のどちらかに大砲を発射、大砲は、レンガ、鉄壁のどちらかに当たるまで直進し、レンガにぶつかると、そのマスは空白になる。
Answer:
レンガのある場所を通りたければ、レンガの前まで来て大砲を撃つだけで良い。
であるから、空白マスへの移動=コスト1、レンガマスへの移動=コスト2のダイクストラで解が求まる。
Source: