すべてのセルを黒に変換するために必要な反復回数を求めるC++プログラム

問題概要

ここでは、黒いセルと白いセルの2種類のセルを含むグリッドが与えられると仮定します。黒いセルは「#」、白いセルは「.」で表され、グリッドは文字列の配列として渡されます。このグリッドに対して、以下の操作を行います。

• 黒いセルと辺を共有している白いセルを黒に変換します。この操作を、グリッド内のすべてのセルが黒になるまで繰り返します。
• すべてのセルを黒に変換するまでに要した反復回数をカウントします。なお、初期状態のグリッドには必ず1つ以上の黒いセルが含まれているものとします。

例として、h = 4、w = 4、grid = {"#...", ".#..", "....", "...#"} という入力を考えてみましょう。

この場合の出力は 3 になります。つまり、すべてのセルを黒に変換するには3回の反復が必要です。

解法のステップ(マルチソース幅優先探索)

この問題は、マルチソースBFS(幅優先探索)を用いることで効率的に解けます。すべての黒いセルを起点として同時にBFSを実行し、各セルが初めて黒くなるまでの距離を記録していきます。最終的な答えは、記録した距離の最大値となります。

具体的には、以下の手順で解きます。

移動方向を表すサイズ4の配列 dx := { 1, 0, -1, 0 }
移動方向を表すサイズ4の配列 dy := { 0, 1, 0, -1 }
2次元配列 distance を定義(すべて -1 で初期化)
整数ペアを格納するキュー q を定義

i := 0 から h 未満の間、1ずつ増やしながら繰り返す:
    j := 0 から w 未満の間、1ずつ増やしながら繰り返す:
        grid[i][j] が '#' と等しい場合:
            distance[i][j] := 0
            ペア (i, j) を q に挿入

q が空でない限り、以下を繰り返す:
    now := q の先頭要素を取り出して削除
    dir := 0 から 4 未満の間、1ずつ増やしながら繰り返す:
        cx := now の1番目の値 + dx[dir]
        cy := now の2番目の値 + dy[dir]
        cx < 0 または cx >= h または cy < 0 または cy >= w の場合はスキップ
        distance[cx][cy] が -1 と等しい場合:
            distance[cx][cy] := distance[now の1番目の値][now の2番目の値] + 1
            ペア (cx, cy) を q に挿入

ans := 0
i := 0 から h 未満の間、1ずつ増やしながら繰り返す:
    j := 0 から w 未満の間、1ずつ増やしながら繰り返す:
        ans := ans と distance[i][j] の最大値
ans を出力する

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

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

void solve(int h, int w, vector<string> grid){
   int dx[4] = { 1, 0, -1, 0 };
   int dy[4] = { 0, 1, 0, -1 };
   vector<vector<int>> distance(h, vector<int>(w, -1));
   queue<pair<int, int>> q;
   for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
         if (grid[i][j] == '#') {
            distance[i][j] = 0;
            q.push(pair<int, int>(i, j));
         }
      }
   }
   while (!q.empty()) {
      auto now = q.front();
      q.pop();
      for (int dir = 0; dir < 4; dir++) {
         int cx = now.first + dx[dir];
         int cy = now.second + dy[dir];
         if (cx < 0 || cx >= h || cy < 0 || cy >= w) continue;
         if (distance[cx][cy] == -1) {
            distance[cx][cy] = distance[now.first][now.second] + 1;
            q.push(pair<int, int>(cx, cy));
         }
      }
   }
   int ans = 0;
   for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
         ans = max(ans, distance[i][j]);
      }
   }
   cout << ans << endl;
}

int main() {
   int h = 4, w = 4;
   vector<string> grid = {"#...", ".#..", "....", "...#"};
   solve(h, w, grid);
   return 0;
}

入力

4, 4, {"#...", ".#..", "....", "...#"}

出力

3