グリッド上に単一のパスを作るためにブロックすべきセル数を求めるC++プログラム

問題の概要

縦 h × 横 w のサイズを持つグリッドが与えられているとします。ロボットはセル (0, 0) の位置からスタートし、(h - 1, w - 1) の位置へ移動する必要があります。グリッドのセルには「ブロックされているセル」と「ブロックされていないセル」の2種類があり、ロボットはブロックされていないセルのみを通過できます。移動は上下左右の4方向が可能です。

ロボットはあるセルから隣接するセルへ任意の方向に移動できるため、スタートからゴールまで複数の経路が存在する可能性があります。本問題では、(0, 0) から (h - 1, w - 1) までの経路を1本だけ残し、その経路に含まれないセルをすべてブロックすることを考えます。このとき、ブロックすべきセルの数を求めて返します。なお、経路がそもそも存在しない場合は -1 を返します。

たとえば、入力が h = 4、w = 4、grid = {"..#", "#.#.", "#.##", "#..."} の場合、出力は 2 になります。つまり、(0, 0) から (3, 3) までの単一のパスを作るには、わずか2つのセルをブロックすればよいことになります。

解き方のアプローチ

この問題は、幅優先探索(BFS)を用いて (0, 0) から (h - 1, w - 1) までの最短経路の長さを求めることで解けます。最短経路が求まれば、次の式でブロックすべきセル数を計算できます。

ブロックすべきセル数 = 通過可能なセル('.')の総数 − 最短経路上のセル数(最短距離 + 1)

具体的なアルゴリズムの手順は以下の通りです。

2次元配列 dp を定義する(各要素は十分大きな値 2500 で初期化)
dp[0, 0] := 0
移動方向を表すペアの配列 moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} を定義する
キュー q を定義し、ペア (0, 0) を挿入する
q が空でない間、以下を繰り返す:
    p := q の先頭要素を取り出す
    i := 0 から 3 まで繰り返す:
        row := p の1番目の値 + moves[i] の1番目の値
        col := p の2番目の値 + moves[i] の2番目の値
        row または col がグリッドの範囲外の場合はスキップ
        grid[row, col] が '#'(ブロック済み)の場合はスキップ
        dp[p の1番目の値, p の2番目の値] + 1 < dp[row, col] の場合:
            dp[row, col] := dp[p の1番目の値, p の2番目の値] + 1
            ペア (row, col) を q に挿入する
dp[h - 1, w - 1] が 2500 のままの場合:
    -1 を返す
count := 0
グリッド全体を走査し、grid[i, j] が '.' であれば count を1増やす
count - (dp[h - 1, w - 1] + 1) を返す

ここで 2500 は「無限大」の代わりとして使われる十分大きな値です。ゴールまでの距離が 2500 のまま更新されない場合は、ゴールに到達できない、すなわち経路が存在しないことを意味します。

実装例

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

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

int solve(int h, int w, vector<string> grid){
   vector<vector<int>> dp(h, vector<int>(w, 2500));
   dp[0][0] = 0;
   vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
   queue<pair<int, int>> q;
   q.push(make_pair(0, 0));
   while (!q.empty()) {
      auto p = q.front();
      q.pop();
      for (int i = 0; i < 4; i++) {
         int row = p.first + moves[i].first;
         int col = p.second + moves[i].second;
         if (row < 0 || row > h - 1 || col < 0 || col > w - 1) continue;
         if (grid[row][col] == '#')
            continue;
         if (dp[p.first][p.second] + 1 < dp[row][col]) {
            dp[row][col] = dp[p.first][p.second] + 1; q.push(make_pair(row, col));
         }
      }
   }
   if (dp[h - 1][w - 1] == 2500) {
      return -1;
   }
   int count = 0;
   for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
         if (grid[i][j] == '.') count++;
      }
   }
   return count - (dp[h - 1][w - 1] + 1);
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"..#", "#.#.", "#.##", "#..."};
   cout<< solve(h, w, grid);
   return 0;
}

入力

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

出力

2

まとめ

このプログラムは、BFSによる最短経路探索とセル数のカウントを組み合わせることで、単一のパスを作成するためにブロックすべきセルの数を効率的に求めます。各セルを高々1度ずつ処理するため、計算量は O(h × w) となり、大きなグリッドでも高速に動作します。