C++で解く「壁と門」問題：BFSによる最短距離計算の徹底解説

問題概要

m × n の2次元グリッドを考えます。このグリッドは、以下の3種類の値で初期化されています。

• -1：壁または障害物
• 0：ゲート（門）
• INF：空き部屋（無限大を表す）

ここでは、INF として 2^31 − 1 = 2147483647 を使用します。ゲートまでの距離は必ず 2147483647 未満になると仮定できるためです。

求めたいのは、各空き部屋に対して、最も近いゲートまでの距離です。もしゲートへ到達できない部屋があれば、その部屋は INF のままにします。

入力例

出力例

解法のアプローチ：多始点BFS

この問題は幅優先探索（BFS）を使うことで効率的に解けます。ポイントは、すべてのゲートを起点として同時に探索を開始し、レベル（距離）ごとに周囲のマスを更新していくことです。こうすることで、各マスには必ず「最も近いゲートからの距離」が書き込まれます。

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

1. 移動方向を表す配列 dir（サイズ 4×2）を {{1,0}, {-1,0}, {0,1}, {0,-1}} として定義する。
2. n := rooms の行数、m := 列数（n が 0 の場合は m も 0）とする。
3. 座標ペアを格納するキュー q を用意する。
4. グリッド全体を走査し、値が 0（ゲート）のマスをすべて q に追加する。
5. lvl := 1 から始め、q が空になるまで以下を繰り返す。
   • sz := 現在の q のサイズとする。
   • sz 回だけ次の処理を行う。
     • q の先頭要素 curr を取り出して削除する。
     • x := curr.first、y := curr.second とする。
     • 4方向それぞれについて、nx := x + dir[i][0]、ny := y + dir[i][1] を計算する。
     • nx < 0 または ny < 0 または nx ≥ n または ny ≥ m または rooms[nx][ny] < lvl の場合は、そのマスをスキップする。
     • rooms[nx][ny] := lvl として距離を更新し、{nx, ny} を q に追加する。

条件「rooms[nx][ny] < lvl」により、すでにより近いゲートから距離が確定済みのマスには上書きしないため、各マスは一度しか更新されません。これが計算量 O(m×n) を実現する鍵です。

C++での実装例

それでは、実際のコードを見てみましょう。

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

void print_vector(vector<vector<auto>> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << "[";
        for(int j = 0; j < v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int n = rooms.size();
        int m = n ? rooms[0].size() : 0;
        queue<pair<int, int>> q;
        // まずすべてのゲートをキューに入れる
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (rooms[i][j] == 0)
                    q.push({ i, j });
            }
        }
        // レベルごとにBFSを実行
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                pair<int, int> curr = q.front();
                q.pop();
                int x = curr.first;
                int y = curr.second;
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl)
                        continue;
                    rooms[nx][ny] = lvl;
                    q.push({ nx, ny });
                }
            }
        }
    }
};

main(){
    vector<vector<int>> v = {{2147483647,-1,0,2147483647}, {2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1}, {0,-1,2147483647,2147483647}};
    Solution ob;
    ob.wallsAndGates(v);
    print_vector(v);
}

実行結果

入力

{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1},{2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}

出力

[[3, -1, 0, 1],[2, 2, 1, -1],[1, -1, 2, -1],[0, -1, 3, 4]]

まとめ

「壁と門」問題は、複数の起点から同時にBFSを行う「多始点BFS」の代表例です。各部屋から個別にゲートを探す素朴な方法では計算量が大きくなりますが、ゲート側から一括で探索を広げることで、O(m×n) の効率的な解法になります。迷路系の最短距離問題全般に応用できるテクニックなので、ぜひ覚えておきましょう。