池の数はいくつか [yukicoder No.697] - はまやんはまやんはまやん

前提知識

解説

連結成分をまとめて1グループとして数え上げていく。
このようにマス目での連結成分をまとめて行く作業はBFSでやるのが定石。
具体的には、左上から順にマスを見ていき、水があれば、そこからBFSをして連結している水を1つのグループとして検知していく。
この際に、二重にカウントしないように、水を抜いておこう。

int H, W, A[3010][3010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    int ans = 0;
    rep(sy, 0, H) rep(sx, 0, W) if (A[sy][sx] == 1) {
        ans++;

        queue<pair<int, int>> que;
        que.push({ sx, sy });
        A[sy][sx] = 0;
        while (!que.empty()) {
            int x = que.front().first;
            int y = que.front().second;
            que.pop();

            rep(i, 0, 4) {
                int xx = x + dx[i];
                int yy = y + dy[i];

                if (0 <= xx and xx < W and 0 <= yy and yy < H) if (A[yy][xx] == 1) {
                    que.push({ xx, yy });
                    A[yy][xx] = 0;
                }
            }
        }
    }
    cout << ans << endl;
}