GCJ2012 Round 1B Problem B. 解き方

Google Code Jam 2012 Round 1B
Problem B. Tide Goes In, Tide Goes Out 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

条件は多くて複雑気味なProblemですが、解き方は割と簡単です。

まず各 square について、そこに入ることができるのはスタートから（潮が干き始めてから）何秒後かを調べます。
最初の水位 H、天井の高さ、床の高さ、水位が下がる速さ（10cm／秒）がわかっているので簡単に計算できます。

次にスタート（左上）からゴール（右下）までの最短経路を求めます。
いろんな計算方法があると思いますが、今回は、より短い時間で進める経路を見つけたときに座標をキューに入れて再探索することで最短経路を見つけたいと思います。

1. まずスタートの座標 (0,0) をキューに入れてループを開始します。(0,0) には水位が下がり始めてから 0.0秒で到達できます。
2. キューから1つ座標を取り出し、その座標の square から左右上下（東西南北）に進めるかチェックします。（ルールに沿って、今いる square の床と進む先の天井、または今いる square の天井と進む先の床が 50cmあいていないとその経路で進むことはできません）
3. 進める場合は 今いる square に到達する最短時間 と 進む先に入ることができる時間 の大きい方を調べます。この時間に、移動にかかる時間（今いる square の床からの水位に応じて1秒または10秒）を加えた時間が、この経路で次の square に到達する時間 です。
4. 進む先の square に至る経路がまだない（進む先に到達する最短時間をまだ持っていない）場合はその時間を記録して、その square から先の経路を調べるべく、進んだ先の座標をキューに入れます。
5. 既に経路を見つけている（進む先に到達する最短時間を持っている）場合は、3.で求めた時間の方が短い場合のみ、その時間を記録して同様に座標をキューに入れます。
6. キューが空になるまで 2. に戻って繰り返します。

問題に「必ず経路がある」書かれているので、キューが空になるときにはゴールまでの経路が見つかっているはずです。

ポイントは 5.の「短い場合のみ」キューに入れる部分。何らかの制御をしないと無限ループになるのは当然ですが、今回のような最短時間を求める場合は、その square に至る最短時間より時間がかかる経路は無視してしまえばよいので、これで調査パターンを減らして高速化します。