C++で解く「可能な限り陸地から遠い」問題 ― マルチソースBFSの実装例

問題概要

N × N のグリッドが与えられ、各セルには 0(水)または 1(陸地)のいずれかが格納されています。この中から「最も近い陸地セルまでの距離」が最大となる水セルを 1 つ見つけ、その距離を返すのが目的です。

距離の計算にはマンハッタン距離を使用します。2 つのセル (x0, y0) と (x1, y1) 間の距離は、次の式で定義されます。

|x0 − x1| + |y0 − y1|

また、グリッド内に陸地が存在しない場合、または水が存在しない場合は -1 を返します。

入力例

この場合の出力は 2 となります。中央のセル (1, 1) は、すべての陸地セルからちょうど距離 2 に位置しており、これ以上遠ざかることができる水セルは存在しないためです。

解法のアプローチ

この問題はマルチソース幅優先探索(BFS)を用いることで効率的に解けます。すべての陸地セルを起点として同時に BFS を展開し、各ステップで新たに到達した水セルに対して、最も近い陸地セルの座標を記録しながら距離を計算していきます。探索全体で得られた最大距離が答えとなります。

手順

• dir := [(1, 0), (-1, 0), (1, -1), (1, 1), (-1, 1), (-1, -1), (0, 1), (0, -1)]

• dir2 := [(1, 0), (-1, 0), (0, 1), (0, -1)](BFS の移動方向として使用)

• map 型の変数 m とキュー q を定義する。n は行数、c は列数とします。

• i を 0 から n − 1 まで繰り返す:

  • j を 0 から n − 1 まで繰り返す:

    • grid[i, j] が 1 の場合、ペア (i, j) を q に挿入し、m[(i, j)] := (i, j) と設定する。

• ret := -1 で初期化する。

• q が空でない限り、以下を繰り返す:

  • sz := q のサイズ

  • sz が 0 でない限り、以下を繰り返す:

    • temp := q の先頭要素を取り出し、削除する。

    • k を 0 から 3 まで繰り返す:

      • nx := temp の第 1 要素 + dir2[k][0]

      • ny := temp の第 2 要素 + dir2[k][1]

      • nx・ny がグリッドの範囲外である場合、または grid[nx][ny] が 1 の場合は、次の反復へスキップする。

      • m[(nx, ny)] := m[temp](最寄りの陸地情報を引き継ぐ)

      • ret := max(calcDist(nx, ny, m[temp]) と ret の大きい方)

      • (nx, ny) を q に挿入する。

      • grid[nx][ny] := 1 に設定する(訪問済みとしてマーク)。

    • sz を 1 減らす。

• ret を返す。

ポイントは、訪問済みの水セルを grid 上で 1 に書き換えることで再訪問を防ぎ、各セルが必ず一度だけ処理されるようにしている点です。これにより計算量は O(N²) に抑えられます。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {
    {1, 0}, {-1, 0}, {1, -1}, {1, 1},
    {-1, 1}, {-1, -1}, {0, 1}, {0, -1}
};
int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
    public:
    int calcDist(int x1, int y1, int x2, int y2){
        return abs(x1 - x2) + abs(y1 - y2);
    }
    int maxDistance(vector<vector<int>>& grid) {
        map < pair <int, int>, pair <int, int> > m;
        queue < pair <int, int> > q;
        int n = grid.size();
        int c = n? grid[0].size() : 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < c; j++){
                if(grid[i][j] == 1){
                    q.push({i, j});
                    m[{i, j}] = {i, j};
                }
            }
        }
        int ret = -1;
        while(!q.empty()){
            int sz = q.size();
            while(sz--){
                pair <int, int> temp = q.front();
                q.pop();
                for(int k = 0; k < 4; k++){
                    int nx = temp.first + dir2[k][0];
                    int ny = temp.second + dir2[k][1];
                    if(nx < 0 || ny < 0 || nx >= n || ny >= c || grid[nx][ny]) continue;
                    m[{nx, ny}] = m[temp];
                    ret = max(calcDist(nx, ny, m[temp].first,
                    m[temp].second), ret);
                    q.push({nx, ny});
                    grid[nx][ny] = 1;
                }
            }
        }
        return ret;
    }
};
main(){
    vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};
    Solution ob;
    cout << (ob.maxDistance(v1));
}

入力

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

出力

2