AtCoder ABC 325 C - Sensors (茶色, 300 点)

またまた登場！！　グラフの連結成分の個数を求める問題！

• 問題へのリンク

問題概要

下図のような のグリッドが与えられる。このグリッドにおいて、上下左右と斜めに隣接している '#' は一つの塊とみなす。

このとき、グリッド内に何個の '#' の塊があるかを答えよ。

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

制約

• 

考えたこと

とても典型的な「連結成分の個数を求めよ」系の問題だ。この手の問題では

• DFS
• BFS
• Union-Find

などの解法が有効だ。ここでは BFS で解いた。計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;  // マスを表す

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; ++i) cin >> S[i];
    
    // マス (sx, sy) を始点とした BFS をするラムダ関数
    vector<vector<int>> dp(H, vector<int>(W, -1));
    auto bfs = [&](int sx, int sy) -> void {
        queue<pint> que;
        que.push(pint(sx, sy));
        dp[sx][sy] = 0;
        while (!que.empty()) {
            auto [x, y] = que.front();
            que.pop();
            for (int x2 = x-1; x2 <= x+1; ++x2) {
                for (int y2 = y-1; y2 <= y+1; ++y2) {
                    if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W) continue;
                    if (S[x2][y2] == '.' || dp[x2][y2] != -1) continue;
                    
                    dp[x2][y2] = dp[x][y] + 1;
                    que.push(pint(x2, y2));
                }
            }
        }
    };
    
    // 各マスを順に見ていく
    int num = 0;
    for (int x = 0; x < H; ++x) {
        for (int y = 0; y < W; ++y) {
            // '#' でないか、すでに探索済みのマスである場合はスキップ
            if (S[x][y] == '.' || dp[x][y] != -1) continue;
            
            // マス (x, y) を始点とした BFS を実施して、そのマスを含む「連結成分」をカウントする
            ++num;
            bfs(x, y);
        }
    }
    cout << num << endl;
}