C++で解く迷路問題：転がるボールが目的地に止まれるかをBFSで判定する方法

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

この問題では、ボールの開始位置、目的地、そして迷路そのものが与えられ、「ボールが目的地の位置で停止できるかどうか」を判定する必要があります。迷路は2次元配列で表現され、1は壁、0は空きスペースを意味します。迷路の外周はすべて壁になっています。開始位置と目的地は行・列のインデックス（座標）で与えられます。

問題例

たとえば、次のような2次元配列で表される迷路を考えてみましょう。

開始位置が (0, 4)、目的地が (4, 4) の場合、出力は true になります。可能な経路の一つは「左へ移動 → 下へ移動 → 右へ移動」という順序です。

解法のアプローチ

この問題は幅優先探索（BFS）を使うことで効率的に解けます。通常のグリッド探索との違いは、ボールが1マスずつではなく「壁に当たるまで一気に滑る」という点です。そのため、各方向について壁に到達するまで座標を進め、最終的な停止位置だけを探索対象としてキューに追加していきます。

具体的な手順は以下の通りです。

1. 開始位置をキューに入れ、訪問済みセットに登録します。
2. キューから現在位置を取り出し、目的地と一致していれば true を返します。
3. 現在位置から上・下・左・右の4方向それぞれについて、壁または境界にぶつかるまで座標を進め、停止位置を求めます。
4. その停止位置が未訪問であれば、訪問済みとしてマークし、キューに追加します。
5. キューが空になるまで処理を続け、目的地に到達できなければ false を返します。

C++による実装例

以下のコードで実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool hasPath(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {
      int n = grid.size();
      int m = grid[0].size();
      queue<vector<int> > q;
      q.push(start);
      set<vector<int> > visited;
      visited.insert(start);
      while (!q.empty()) {
         vector<int> curr = q.front();
         q.pop();
         int x = curr[0];
         int y = curr[1];
         if (destination[0] == x && destination[1] == y)
            return true;
         int i = x;
         while (i + 1 < n && !grid[i + 1][y])
            i++;
         if (!visited.count({ i, y })) {
            visited.insert({ i, y });
            q.push({ i, y });
         }
         i = x;
         while (i - 1 >= 0 && !grid[i - 1][y])
            i--;
         if (!visited.count({ i, y })) {
            visited.insert({ i, y });
            q.push({ i, y });
         }
         i = y;
         while (i + 1 < m && !grid[x][i + 1])
            i++;
         if (!visited.count({ x, i })) {
            visited.insert({ x, i });
            q.push({ x, i });
         }
         i = y;
         while (i - 1 >= 0 && !grid[x][i - 1])
            i--;
         if (!visited.count({ x, i })) {
            visited.insert({ x, i });
            q.push({ x, i });
         }
      }
      return false;
   }
};
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.hasPath(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}

出力

1

コードのポイント

• BFSの採用： キューを使って探索することで、到達可能な停止位置を漏れなく効率的に調べられます。
• 訪問済み管理： set で既に探索した停止位置を記録することにより、同じ場所を何度も探索する無駄を防ぎ、無限ループを回避できます。
• 滑る動作のシミュレーション： 各方向に対して while ループで壁の手前まで座標を進めることで、「壁にぶつかるまで転がる」という挙動を正確に再現しています。

計算量は迷路のサイズを N×M とすると、各セルからの4方向へのスライドを考慮して O(N×M×max(N,M)) 程度となり、一般的な入力サイズに対して十分高速に動作します。