C++で解く「全ての建物からの最短距離」問題 ― BFSによる効率的なアプローチ

問題概要

空き地に家を建てることを考えてみましょう。条件は、その家からすべての建物へ移動する距離の合計が最小になることです。移動は上下左右の4方向のみ許されます。

盤面は、0・1・2 のいずれかの値を持つ2次元グリッドとして与えられます。それぞれの意味は次の通りです。

• 0：自由に通行できる空き地
• 1：通行できない建物
• 2：通行できない障害物

入力例と出力例

例として、次のグリッドが与えられたとします。

この場合の出力は 7 です。3つの建物が (0,0)、(0,4)、(2,2) の位置にあり、障害物が (0,2) に存在します。そこで (1,2) が家を建てるのに最適な空き地となり、各建物までの距離の合計は 3 + 3 + 1 = 7 で、これが最小値になります。

解法のアイデア：各建物からBFSを行う

この問題は、各建物を起点とした幅優先探索（BFS）によって効率よく解くことができます。各建物から順に探索し、すべての空き地マスに対して「その建物からの距離」と「到達できた建物の数」を累積していきます。最終的に、すべての建物から到達可能な空き地の中で、累積距離が最小のものが答えとなります。

アルゴリズムの手順

1. 答え ret を無限大（INT_MAX）で初期化します。
2. 行数 n、列数 m を取得し、建物の数を数える変数 numberOfOnes を 0 で初期化します。
3. 累積距離を記録する n × m の2次元配列 dist と、到達した建物の数を記録する同サイズの配列 reach を用意します。
4. 各建物 (i, j) について、次のBFSを実行します。
   • キューに {i, j} を入れ、訪問済み集合 visited を用意します。
   • lvl（現在の距離）を 1 から始め、キューが空になるまで層ごとに処理します。
   • キューから取り出したセル (x, y) の4近傍 (nx, ny) について、範囲外・訪問済み・空き地（0）以外ならスキップします。
   • 有効なセルには dist[nx][ny] += lvl を加算し、reach[nx][ny] をインクリメントしてキューに追加します。
5. 全マスを走査し、grid[i][j] == 0 かつ reach[i][j] == numberOfOnes（すべての建物から到達可能な空き地）であるマスについて、ret := min(ret, dist[i][j]) を更新します。
6. ret が更新されていなければ -1 を、そうでなければ ret を返します。

C++による実装例

理解を深めるために、次の実装を見てみましょう。

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int ret = INT_MAX;
        int n = grid.size();
        int m = grid[0].size();
        int numberOfOnes = 0;
        vector<vector<int>> dist(n, vector<int>(m));
        vector<vector<int>> reach(n, vector<int>(m));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1){
                    numberOfOnes++;
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    set<pair<int, int>> visited;
                    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 k = 0; k < 4; k++){
                                int nx = x + dir[k][0];
                                int ny = y + dir[k][1];
                                if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;
                                visited.insert({nx, ny});
                                dist[nx][ny] += lvl;
                                reach[nx][ny]++;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){
                    ret = min(ret, dist[i][j]);
                }
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

計算量の目安

建物の数を B、グリッドのサイズを N × M とすると、各建物ごとのBFSは O(N × M) かかるため、全体の時間計算量は O(B × N × M)（最悪ケースで O((N × M)²)）となります。dist・reach・visited などの補助データ構造により、必要なメモリは O(N × M) です。

入力

[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

出力

7