C++で解く「迷路 II」問題 ― 壁に当たるまで転がるボールの最短距離をBFSで求める

問題概要

空きマスと壁からなる迷路の中にボールがあります。ボールは上・下・左・右のいずれかの方向に転がって空きマスを進むことができますが、壁にぶつかるまで止まることはできません。ボールが停止したときに、初めて次の方向を選ぶことができます。

ボールのスタート位置、目的地、そして迷路そのものが与えられるので、ボールが目的地で停止するまでの最短距離を求めてください。ここでの距離とは、ボールが転がって通過した空きマスの数のことです（スタート位置は含まず、目的地は含みます）。どうしても目的地で停止できない場合は -1 を返します。

迷路は2次元配列で表現されます。1 が壁、0 が空きスペースを意味し、迷路の外周はすべて壁になっています。スタート位置と目的地の座標は行・列のインデックスで与えられます。

入力例

たとえば、次のような2次元配列で迷路が表されているとします。

このとき、スタート位置が (0, 4)、目的地が (4, 4) であれば、出力は 12 になります。可能な移動経路の一つは「左 → 下 → 左 → 下 → 右 → 下 → 右」で、(1+1+3+1+2+2+2) = 12 となります。

解き方のアプローチ

この問題は、各マスへの最短距離を管理しながら幅優先探索（BFS）を行うことで解けます。重要なポイントは、ボールが1回の転がりで進む距離（コスト）が方向や位置によって異なるため、単純なBFSではなく、より短い距離が見つかった場合にキューへ再登録する「距離の緩和（リラクゼーション）」を行う点です。具体的な手順は以下の通りです。

• n := 行数、m := 列数 とする
• ret := 無限大（INT_MAX）で初期化する
• n × m の2次元配列 dist を定義し、全要素を無限大で初期化する
• キュー q を定義し、スタート位置を挿入する
• dist[start[0]][start[1]] := 0 とする
• q が空になるまで、以下を繰り返す
  • curr := q の先頭要素を取り出し、q から削除する
  • x := curr[0]、y := curr[1] とする
  • (x, y) が目的地と一致していれば、ret := min(ret, dist[x][y]) で答えを更新する
  • currDist := dist[x][y] とする
  • 下方向：i := x とし、grid[i+1][y] が 0 の間 i++ しながら tempDist++ を繰り返す。currDist + tempDist < dist[i][y] であれば dist[i][y] を更新し、{i, y} をキューに追加する
  • 上方向：同様に、grid[i-1][y] が 0 の間 i-- しながら処理する
  • 左方向：grid[x][i-1] が 0 の間 i-- しながら処理する
  • 右方向：grid[x][i+1] が 0 の間 i++ しながら処理する

最後に、ret が無限大のままなら -1 を、そうでなければ ret を返します。

C++による実装例

それでは、実際の実装を見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int shortestDistance(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination){
      int n = grid.size();
      int m = n ? grid[0].size() : 0;
      int ret = INT_MAX;
      vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
      queue<vector<int>> q;
      q.push(start);
      dist[start[0]][start[1]] = 0;
      while(!q.empty()){
         vector<int> curr = q.front();
         q.pop();
         int x = curr[0];
         int y = curr[1];
         if(x == destination[0] && y == destination[1]){
            ret = min(ret, dist[x][y]);
         }
         int currDist = dist[x][y];
         int tempDist = 0;
         int i = x;
         while(i + 1 < n && !grid[i + 1][y]){ // 下方向へ転がす
            i++;
            tempDist++;
         }
         if(currDist + tempDist < dist[i][y]){
            dist[i][y] = currDist + tempDist;
            q.push({i, y});
         }
         i = x;
         tempDist = 0;
         while(i - 1 >= 0 && !grid[i - 1][y]){ // 上方向へ転がす
            tempDist++;
            i--;
         }
         if(currDist + tempDist < dist[i][y]){
            dist[i][y] = currDist + tempDist;
            q.push({i, y});
         }
         i = y;
         tempDist = 0;
         while(i - 1 >= 0 && !grid[x][i - 1]){ // 左方向へ転がす
            i--;
            tempDist++;
         }
         if(currDist + tempDist < dist[x][i]){
            dist[x][i] = currDist + tempDist;
            q.push({x, i});
         }
         i = y;
         tempDist = 0;
         while(i + 1 < m && !grid[x][i + 1]){ // 右方向へ転がす
            i++;
            tempDist++;
         }
         if(currDist + tempDist < dist[x][i]){
            dist[x][i] = currDist + tempDist;
            q.push({x, i});
         }
      }
      return ret == INT_MAX ? -1 : ret;
   }
};
int main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
   vector<int> v1 = {0,4}, v2 = {4,4};
   cout << ob.shortestDistance(v, v1, v2);
}

実行結果

入力

{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}}, {0,4}, {4,4}

出力

12

計算量

時間計算量：O(n × m × max(n, m)) ― 各マスから最大4方向へボールを転がす処理を行うためです。
空間計算量：O(n × m) ― 各マスの最短距離を保持する dist 配列とキューが必要になります。