グリッド＋多視点BFS ABC 383 C - Humidifier 3を理解し忘れないようにする

https://atcoder.jp/contests/abc383/tasks/abc383_c

問題概要

AtCoder社のオフィスは H 行 W 列のマス目で表される。
各マスの状態は文字 $S{\tiny i,j}$で表され、$S{\tiny i,j}$が # のときそのマスは壁、. のときそのマスは床、H のときそのマスは加湿器が置かれた床です。
あるマスは、ある加湿器から壁を通らず上下左右に D 回以下の移動で辿り着ける場合加湿されます。ここで、加湿器が置かれた床のマスは必ず加湿されている、壁は加湿されないことに注意。

加湿されている床のマスの個数を求めてください。

制約

$1≤H≤1000$
$1≤W≤1000$
$0≤D≤H×W$
$Si,j$は # または . または H である (1≤i≤H,1≤j≤W)
入力される数値は全て整数

基本設計(解説見た)

公式の解説を参考にしました。
https://atcoder.jp/contests/abc383/editorial/11544

通常のBFSを使った場合

加湿器（始点）が１つならこちらの迷路の問題のように通常のBFSで解ける。本問題は加湿器がN個あるので、それを１個ずつ通常のBFSしていく場合、計算量は加湿器を探すためにグリッドを回すHW回とBFSのHWでO(HWHW)となる。

計算量O(HWHW)の解消方法

加湿器N個を先にキューに入れてからBFSを行う。メモする量は最大でもグリッドの数なので、計算量はO(HW)

提出コード

提出コード

省略

// 四方向への移動を表すベクトル
// 下、右、上、左の順
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};

int main()
{
  int h,w,D;
  cin >> h >> w >> D;
  vector<string> s(h);
  rep(i,h) cin >> s[i];
  vector dist(h,vector<int>(w,-1));
  queue<P<int>> que; 
  rep(i,h) rep(j,w) {
    if (s[i][j] != 'H') continue;
    dist[i][j] = 0;
    que.emplace(i,j);
  }

  while (!que.empty())
  {
    auto [x,y] = que.front();
    que.pop();
    rep(d,4) {
      int x2 = x + dx[d];
      int y2 = y + dy[d];
      // 配列外参照の対応
      if (x2 < 0 || x2 >= h || y2 < 0 || y2 >= w) continue;
      // 壁は計算しない。
      if (s[x2][y2] == '#') continue;
      // すでにメモしたマスは更新しない。
      if (dist[x2][y2] != -1) continue;
      dist[x2][y2] = dist[x][y] + 1;
      que.emplace(x2,y2);
    }
  }
  int ans = 0;
  rep(x,h) rep(y,w) {
    if (dist[x][y] >= 0 && dist[x][y] <= D) ans++;
  }
  cout << ans << endl;
  return 0;
}