C++で解くバイナリ行列の最短経路問題 ― BFSによる実装方法を徹底解説

バイナリ行列の最短経路問題とは

N×N の正方形グリッドを考えます。各セルは「空き(0)」または「ブロック(1)」のいずれかです。左上から右下へのクリアパスの長さが k であるとは、そのパスがセル C₁, C₂, …, C_k で構成され、次の条件をすべて満たすことを指します。

• 隣接するセル C_i と C_i+1 は8方向(上下左右+斜め)につながっている。つまり互いに異なり、辺または角を共有している。
• C₁ は位置 (0, 0) にある。
• C_k は位置 (N−1, N−1) にある。
• C_i が位置 (r, c) にあるとき、grid[r][c] は空き、すなわち 0 である。

この記事では、左上から右下までの最短のクリアパスの長さを求める方法を解説します。そのようなパスが存在しない場合は −1 を返します。

具体例

たとえば、次のような3×3のグリッドを考えてみましょう。

この場合、右側の列に沿って斜め移動を組み合わせることでゴールに到達でき、最短距離は 4 となります。

解法アプローチ:幅優先探索(BFS)

この問題は、重みのないグラフ上の最短路を求めるのに適した幅優先探索(BFS)を使うことで効率的に解けます。アルゴリズムの手順は以下の通りです。

• 8方向へ移動するための方向配列を定義します。中身は [[1,1], [1,-1], [-1,1], [1,0], [0,1], [-1,-1], [0,-1], [-1,0]] です。
• メイン処理ではグリッドを受け取り、以下のように動作します。
• 点を格納するキュー q と、行数 n を定義します。
• grid[0][0] が 0 の場合、新しい点 p(0, 0, 1)(座標と現在のパス長)を生成して q に追加し、grid[0][0] を 1 に更新します。これは「訪問済み」マークを兼ねています。
• q が空でない限り、以下を繰り返します。
  • キューの先頭の点を curr として取り出し、削除します。
  • x := curr の x 座標、y := curr の y 座標、c := curr の保持するパス長とします。
  • x = n−1 かつ y = n−1(右下に到達)であれば、c を返します。
  • c を 1 増やします。
  • i を 0 から 7 までループします。
    • X := x + d[i][0]、Y := y + d[i][1] とします。
    • X・Y がともに 0 以上 n 未満の範囲内にあり、かつ grid[X][Y] が 0 であれば、grid[X][Y] を 1 にして、新しい点 p(X, Y, c) を q に追加します。
• キューが空になってもゴールに届かなければ、−1 を返します。

BFSでは距離が近い順に探索が進むため、最初にゴールへ到達した時点のパス長が必ず最短になります。また、訪問済みセルを 1 で埋めて再訪を防ぐことで、同じセルの二重処理を回避できます。

C++での実装例

以下に実際のコードを示します。

#include <bits/stdc++.h>
using namespace std;
int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1},
{0, -1}, {-1, 0}};
struct point{
    int x, y, c;
    point(int a, int b, int z){
        x = a;
        y = b;
        c = z;
    }
};
class Solution {
    public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        queue <point> q;
        int n = grid.size();
        if(!grid[0][0]){
            q.push(point(0, 0, 1));
            grid[0][0] = 1;
        }
        while(!q.empty()){
            point curr = q.front();
            q.pop();
            int x = curr.x;
            int y = curr.y;
            int c = curr.c;
            if(x == n-1 && y == n-1)return c;
               c++;
            for(int i = 0; i < 8; i++){
                int X = x + d[i][0];
                int Y = y + d[i][1];
                if(X >= 0 && X < n && Y >= 0 && Y < n &&
                !grid[X][Y]){
                    grid[X][Y] = 1;
                    q.push(point(X, Y, c));
                }
            }
        }
        return -1;
    }
};
main(){
    vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
    Solution ob;
    cout << (ob.shortestPathBinaryMatrix(v));
}

入力

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

出力

4

計算量について

このアルゴリズムでは、各セルは最大でも一度しかキューに追加されないため、時間計算量は O(N²)、訪問状態をグリッド自体に記録するため追加の空間計算量も O(N²)(キュー分)となります。N×N のグリッド全体を効率よく走査できる、非常にシンプルかつ実用的な手法です。