SRM646 div2 500

問題

2次元グリッドの原点にいて、グリッドに沿って動ける。
毎秒、その場にとどまるか、上下左右に1単位だけ動けるが、いくつかの格子点が通行禁止になっている。
k秒間で、x座標が最大となる点でのx座標の値を求める。

通行禁止の格子点数 <= 47
-10^3 <= 格子点座標x,y <= 10^3
1<=k<=10^3

考え方

メモしながらBFSで全探索。

ある時刻にある点に居る時に、上下左右にうごけるが、すでにその点に訪れている場合は、とどまり続ければ同じことなので、考える必要がない。