実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 750

問題概要

$H \times W$ のマス目があり、上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表す。各マスの状態は文字 $S_{i,j}$ で表され、 $S_{i,j} =$ # のときそのマスは壁、.のときそのマスは床、Hのときそのマスは加湿器が置かれた床である。

あるマスは、ある加湿器から壁を通らず上下左右に $D$ 回以下の移動で辿り着ける場合加湿される。ここで、加湿器が置かれた床のマスは必ず加湿されている。

このとき、加湿されている床のマスの個数を求めよ。

制約

入力される数値は全て整数。
$1 \leq H \leq 1000$
$1 \leq W \leq 1000$
$0 \leq D \leq H\times W$

考察

見るからに BFS をしろという雰囲気だが、今回は探索開始点が加湿器のマスなので、「多始点 BFS」ということになる。

ただこの場合もやることは変わらず、加湿器のマスをqueueに突っ込んで、そこからはいつもの BFS をするだけ。実装詳細はコードを参照のこと。

コード

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

// ======================================== //

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    int H, W, D;
    cin >> H >> W >> D;
    vector<string> S(H);
    rep(i, 0, H) cin >> S[i];

    vector<vector<bool>> isHumid(H, vector<bool>(W, false));
    queue<tuple<int, int, int>> queue;
    rep(i, 0, H)
    {
        rep(j, 0, W)
        {
            if (S[i][j] == 'H')
            {
                queue.emplace(i, j, 0);
                isHumid[i][j] = true;
            }
        }
    }

    while (!queue.empty())
    {
        auto [x, y, dist] = queue.front();
        queue.pop();

        if (dist >= D)
            continue;

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

            if (nx < 0 || nx >= H || ny < 0 || ny >= W || S[nx][ny] == '#' || isHumid[nx][ny])
                continue;

            isHumid[nx][ny] = true;
            queue.emplace(nx, ny, dist + 1);
        }
    }

    int ans = 0;
    rep(i, 0, H) rep(j, 0, W) if (isHumid[i][j]) ans++;

    cout << ans << endl;
}