http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4416724
- 互いに行き来できる=頂点の到達可能性=BFSかDFSで到達した頂点に印を付ける
互いに行き来できるということは、グリッドをグラフに変換したときに閉路が存在するということなので強連結成分分解して求めることも出来るが、もっと単純にDFSやBFSで求めることが出来る。任意の座標をスタート地点としてBFS(またはDFS)して到達した頂点集合を島1個分とカウントすれば良い。制約からの処理が可能なので、各グリッド全てをスタート地点としてBFSしてもTLEせず処理できる。BFSの具体的な実装としては、8方向で移動して移動済み頂点に印を付けていけば良い。