Submission #46816512

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/dsu>

bool grid[1009][1009];

void solve(std::istream& is, std::ostream& os) {
    using Num = long long int;
    Num h {0};
    Num w {0};
    is >> h >> w;

    for(Num y{0}; y<h; ++y) {
        std::string s;
        is >> s;
        for(Num x{0}; x<w; ++x) {
            if (s.at(x) == '#') {
                grid[y][x] = true;
            }
        }
    }

    atcoder::dsu group(h*w);

    for(Num y{0}; y<(h-1); ++y) {
        for(Num x{0}; x<w; ++x) {
            if (!grid[y][x]) {
                continue;
            }

            const auto u = y * w + x;
            if (grid[y+1][x]) {
                const auto v = (y+1) * w + x;
                group.merge(u, v);
            }
        }
    }

    for(Num y{0}; y<(h-1); ++y) {
        for(Num x{0}; x<(w-1); ++x) {
            if (!grid[y][x]) {
                continue;
            }

            const auto u = y * w + x;
            if (grid[y+1][x+1]) {
                const auto v = (y+1) * w + x + 1;
                group.merge(u, v);
            }
        }
    }

    for(Num y{0}; y<h; ++y) {
        for(Num x{0}; x<(w-1); ++x) {
            if (!grid[y][x]) {
                continue;
            }

            const auto u = y * w + x;
            if (grid[y][x+1]) {
                const auto v = y * w + x + 1;
                group.merge(u, v);
            }
        }
    }

    for(Num y{0}; y<(h-1); ++y) {
        for(Num x{1}; x<w; ++x) {
            if (!grid[y][x]) {
                continue;
            }

            const auto u = y * w + x;
            if (grid[y+1][x-1]) {
                const auto v = (y+1) * w + x - 1;
                group.merge(u, v);
            }
        }
    }

    Num answer {0};
    for(const auto& vec : group.groups()) {
        const auto p = vec.at(0);
        const auto y = p / w;
        const auto x = p % w;
        if (grid[y][x]) {
            ++answer;
        }
    }

    os << answer << "\n";
    return;
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result