C++でマトリックスを幅優先探索（BFS）して最短距離を求める方法

2次元マトリックス（行列）上の各セルには、左・右・下・上という4つの方向が存在します。幅優先探索（Breadth First Search、BFS）とは、与えられた2次元行列の中で2つの要素間の最短距離を見つけるためのアルゴリズムです。

各セルでは4方向への移動が考えられ、行列内のセルの状態は以下の4つの数値で表現されます。

• 「2」 … そのセルがスタート地点（Source）であることを示します。
• 「3」 … そのセルがゴール地点（Destination）であることを示します。
• 「1」 … そのセルは任意の方向へ移動可能であることを示します。
• 「0」 … そのセルはどの方向にも移動できないことを示します。

これらの条件に基づいて、与えられたマトリックスに対して幅優先探索を実行することができます。

この問題へのアプローチ

マトリックス全体を走査し、BFSを用いてセル間の最短距離を求めるアルゴリズムは以下の手順で実装します。

1. まず行数と列数を入力として受け取ります。
2. 指定された行数・列数でマトリックスを初期化します。
3. 整数型関数 shortestDist(int row, int col, int mat[][col]) が行・列・マトリックスを引数として受け取り、要素間の最短距離を返します。
4. 変数 source と destination を初期化し、スタート地点とゴール地点となる要素を特定します。
5. 要素が「3」であればゴール地点として、「2」であればスタート地点として記録します。
6. キュー（queue）データ構造を初期化し、マトリックスに対してBFSを実装します。
7. マトリックスの行と列の情報をペアとしてキューに挿入します。セルを順に取り出しながら、それがゴールセルかどうかを判定し、現在のセルよりも短い距離でゴールに到達できる場合は距離を更新します。
8. さらに別の方向へも移動を試み、現在のセルからの最小距離を求めます。
9. 最終的な最短距離を出力として返します。

C++実装例

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

int findDistance(int row, int col, int mat[][5]) {
    int source_i, source_j, destination_i, destination_j;

    // スタート地点とゴール地点を探す
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (mat[i][j] == 2) {
                source_i = i;
                source_j = j;
            }
            if (mat[i][j] == 3) {
                destination_i = i;
                destination_j = j;
            }
        }
    }

    // 距離配列を無限大（INT_MAX）で初期化
    int dist[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            dist[i][j] = INT_MAX;
    }

    // BFS用のキューを初期化
    queue<pair<int, int>> q;
    q.push(make_pair(source_i, source_j));
    dist[source_i][source_j] = 0;

    // 移動制約のチェックを加えたBFS
    while (!q.empty()) {
        int x = q.front().first;   // セルの行（x座標）
        int y = q.front().second;  // セルの列（y座標）
        q.pop();

        // 左へ移動できる場合
        if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
            if (dist[x][y] + 1 < dist[x][y - 1]) {
                dist[x][y - 1] = dist[x][y] + 1;
                q.push(make_pair(x, y - 1));
            }
        }
        // 右へ移動できる場合
        if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
            if (dist[x][y] + 1 < dist[x][y + 1]) {
                dist[x][y + 1] = dist[x][y] + 1;
                q.push(make_pair(x, y + 1));
            }
        }
        // 上へ移動できる場合
        if (x - 1 >= 0 && (mat[x - 1][y] == 1 || mat[x - 1][y] == 3)) {
            if (dist[x][y] + 1 < dist[x - 1][y]) {
                dist[x - 1][y] = dist[x][y] + 1;
                q.push(make_pair(x - 1, y));
            }
        }
        // 下へ移動できる場合
        if (x + 1 < row && (mat[x + 1][y] == 1 || mat[x + 1][y] == 3)) {
            if (dist[x][y] + 1 < dist[x + 1][y]) {
                dist[x + 1][y] = dist[x][y] + 1;
                q.push(make_pair(x + 1, y));
            }
        }
    }
    return dist[destination_i][destination_j];
}

int main() {
    // 行数と列数の初期化
    int row = 5;
    int col = 5;
    // マトリックスの初期化
    int mat[][5] = {
        {1, 0, 0, 2, 1},
        {1, 0, 1, 1, 1},
        {0, 1, 1, 2, 0},
        {3, 1, 0, 0, 1},
        {1, 1, 0, 0, 1}
    };
    int answer = findDistance(row, col, mat);
    // スタートとゴールが到達不能な場合
    if (answer == INT_MAX)
        cout << "経路が見つかりませんでした" << endl;
    else {
        cout << "スタートからゴールまでの最短距離:" << endl;
        cout << answer << endl;
    }
    return 0;
}

出力結果

スタートからゴールまでの最短距離:
4

計算量について

このアルゴリズムでは、各セルを最大でも定数回ずつキューに追加するため、時間計算量は O(row × col) となります。また、距離配列とキューのために O(row × col) の空間計算量が必要です。スタートからゴールへの経路が存在しない場合、距離は INT_MAX のまま残るため、「経路なし」として判定できます。