C++プログラム：グリッド上の移動可能なセル間の最大移動回数を求める方法

問題の概要

高さ h × 幅 w のグリッドが与えられます。グリッドには「ブロックされたセル（壁）」と「ブロックされていないセル（通路）」の2種類があり、2次元配列として表現されます。ブロックされたセルは '#'、ブロックされていないセルは '.' で示されます。

このグリッド上で、ある通路セルから別の通路セルへ移動することを考えます。移動できるのは上下左右の4方向のみで、斜め移動は禁止されています。また、通過できるのは '.' のセルだけです。この条件のもとで、あるセルから別のセルへ到達するために必要な最大の移動回数を求めるのが本記事の目的です。

入力例

たとえば、h = 4、w = 4、grid = {"..#.", "#.#.", "..##", "###."} の場合、出力は 4 になります。これは、セル (0,0) からセル (2,0) へ到達するのに最大 4 回の移動が必要であることを意味します。

解法のアプローチ：幅優先探索（BFS）

この問題は幅優先探索（BFS）を用いて解くことができます。基本的なアイデアは以下の通りです。

• グリッド上の各 '.' セルを起点としてBFSを実行し、他のすべての通路セルへの最短距離を計算します。
• すべての起点の中で得られた距離の最大値が、求める「最大移動回数」となります。

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

1. 上下左右の移動方向を表す配列 xdir、ydir を定義します。
2. 距離を記録する2次元配列 dist と、初期化用の配列 reset を用意します。
3. 各セルを走査し、'.' であればそこを起点にBFSを開始します。
4. BFSの処理中に到達したセルの距離を順次更新し、その最大値を res に記録します。
5. 最後に res を返します。

擬似コード

サイズ4の配列 xdir := {1, 0, -1, 0} を定義
サイズ4の配列 ydir := {0, 1, 0, -1} を定義
2次元配列 dist を定義
2次元配列 reset を定義
res := 0
i := 0 から i < h の間、i を1ずつ増やしながら繰り返し:
    j := 0 から j < w の間、j を1ずつ増やしながら繰り返し:
        dist := reset
        grid[i][j] が '.' と等しい場合:
            dist[i][j] := 0
            整数ペアを格納するキュー q を定義
            make_pair(i, j) を q に挿入
            q が空でない間、繰り返し:
                x := q の先頭要素の1番目の値
                y := q の先頭要素の2番目の値
                res := dist[x][y] と res の最大値
                q から先頭要素を削除
                k := 0 から k < 4 の間、k を1ずつ増やしながら繰り返し:
                    px := x + xdir[k]
                    py := y + ydir[k]
                    px >= 0 かつ px < h かつ py >= 0 かつ py < w の場合:
                        grid[px][py] が '.' と等しい場合:
                            dist[px][py] が -1 と等しい場合:
                                dist[px][py] := dist[x][y] + 1
                                ペア(px, py) を q に挿入
return res

C++での実装例

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

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

int solve(int h, int w, vector<string> grid){
    int xdir[4] = {1, 0, -1, 0};
    int ydir[4] = {0, 1, 0, -1};
    vector<vector<int>> dist(h, vector<int>(w, -1));
    vector<vector<int>> reset(h, vector<int>(w, -1));
    int res = 0;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            dist = reset;
            if(grid[i][j] == '.'){
                dist[i][j] = 0;
                queue<pair<int,int>> q;
                q.push(make_pair(i, j));
                while(!q.empty()){
                    int x = q.front().first;
                    int y = q.front().second;
                    res = max(dist[x][y], res);
                    q.pop();
                    for(int k = 0; k < 4; k++){
                        int px = x + xdir[k];
                        int py = y + ydir[k];
                        if(px >= 0 && px < h && py >= 0 && py < w){
                            if(grid[px][py] == '.'){
                                if(dist[px][py] == -1){
                                    dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py));
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return res;
}
int main() {
    int h = 4, w = 4;
    vector<string> grid = {"..#.", "#.#.", "..##", "###."};
    cout << solve(h, w, grid);
    return 0;
}

実行結果

入力

4, 4, {"..#.", "#.#.", "..##", "###."}

出力

4

計算量の目安

この実装では、すべての '.' セルを起点としてBFSを実行しています。BFS1回あたりの計算量は O(h×w)、起点の候補も最大 h×w 個あるため、全体の時間計算量は O((h×w)²) となります。小〜中規模のグリッドであれば十分実用的な速度で動作しますが、グリッドが非常に大きい場合は、より効率的な手法（例えば双方向探索やグラフの直径を推定するテクニック）を検討するとよいでしょう。

まとめ

本記事では、壁を避けながら上下左右にのみ移動できるグリッド上で、ある通路セルから別の通路セルへの最大移動回数を求める問題を扱いました。全セルを起点とした幅優先探索により、確実に正しい答えを得ることができます。BFSによる最短距離計算の応用例として、ぜひ参考にしてください。