POJ3669 Meteor Shower 解説

POJ3669 Meteor Shower

http://poj.org/problem?id=3669

問題文

ベッシーは始め座標(0, 0)にいます。M個の隕石が(x, y)にT秒の時に落ちてきます。隕石が落ちた場所とその隣接する四方のマスには移動できません。ベッシーが安全な場所に移動する時、最短経路を行った場合、何秒かかるかを計算しなさい。

解法

ただのBFSですが、少しバグらせるポイントがあります。（実際少しバグらせた）座標がマイナスになることはありませんが、プラス方向には無限に続きます。