ABC241 F - Skate (500)
H,Wが大きいので盤面の状態を全部持っておくことはできない
止まる可能性があるのは障害物の隣のマスだけであることが分かる
ゴールがこれに当てはまらない場合は到達不可能
障害物を列毎、行毎にSetで管理する
スタート地点をキューに入れる
キューが空になるまで以下を行う
キューの先頭を取る
現在地点の上下左右の障害物をSetから探し、現在地点の方に1マスずらしたところを次の候補とする
既に訪れていた場合は飛ばす
最終的にゴールを訪れていればその移動回数、訪れなければ-1を出力
探索する点の個数は$ \mathcal{O}(N)でそれぞれ二分探索するので全体で$ \mathcal{O}(N \log N)
解説の先に列挙する方法だと$ O(N)