C++でマトリックス（行列）内の2つのセル間にパスが存在するかを判定する方法

本記事では、与えられたマトリックス（行列）の中に、2つのセルをつなぐパス（経路）が存在するかどうかを判定するC++プログラムについて解説します。

ここでは、0・1・2・3のいずれかの値を持つ正方行列が与えられたと仮定します。各値の意味は以下の通りです。

• 0：空白の壁（通過不可）
• 1：スタート地点（ソース）
• 2：ゴール地点（デスティネーション）
• 3：空白セル（通過可能）

マトリックス内にはソースとデスティネーションがそれぞれ1つだけ存在します。このプログラムの目的は、上下左右の4方向のみに移動し（斜め移動は禁止）、ソースからデスティネーションへ到達できる経路があるかどうかを確認することです。

解決のアプローチ

この問題は、マトリックスをグラフとして捉えることで効率的に解けます。各セルをグラフの頂点とみなし、隣接する通行可能なセル同士を辺で結びます。その後、幅優先探索（BFS）を用いて、ソースからデスティネーションへの到達可能性を調べます。

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

1. マトリックスの各セルに一意の番号（頂点ID）を割り当てます。
2. 通行可能なセル（値が0以外）について、上下左右の隣接セルが通行可能であれば、対応する頂点間に辺を追加します。
3. 値が1のセルをソース、値が2のセルをデスティネーションとして記録します。
4. BFSを実行し、ソースからデスティネーションに到達できれば「Possible」、そうでなければ「Not Possible」を出力します。

C++コード例

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

// 与えられた配列からグラフを作成するクラス
class use_graph {
    int W;
    list <int> *adj;
    public :
    use_graph( int W ){
        this->W = W;
        adj = new list<int>[W];
    }
    void add_side( int source , int dest );
    bool search ( int source , int dest);
};

// 辺を追加する関数
void use_graph :: add_side ( int source , int dest ){
    adj[source].push_back(dest);
    adj[dest].push_back(source);
}

// BFS（幅優先探索）を実行する関数
bool use_graph :: search(int source, int dest) {
    if (source == dest)
        return true;
    // 訪問済みフラグの初期化
    bool *visited = new bool[W];
    for (int i = 0; i < W; i++)
        visited[i] = false;
    list<int> queue;
    // ソースを訪問済みとしてマークし、キューに追加
    visited[source] = true;
    queue.push_back(source);
    // 隣接する頂点へ移動
    list<int>::iterator i;
    while (!queue.empty()){
        source = queue.front();
        queue.pop_front();
        for(i=adj[source].begin();i!=adj[source].end(); ++i) {
            if (*i == dest)
                return true;
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push_back(*i);
            }
        }
    }
    // デスティネーションに到達できなかった場合
    return false;
}

// 移動先のセルが有効かどうかを判定する関数
bool is_okay(int i, int j, int M[][4]) {
    if ((i < 0 || i >= 4) || (j < 0 || j >= 4 ) || M[i][j] == 0)
        return false;
    return true;
}

// パスの存在を確認するメイン関数
bool find(int M[][4]) {
    int source , dest ;
    int W = 4*4+2;
    use_graph g(W);
    int k = 1 ;
    for (int i =0 ; i < 4 ; i++){
        for (int j = 0 ; j < 4; j++){
            if (M[i][j] != 0){
                if ( is_okay ( i , j+1 , M ) )
                    g.add_side ( k , k+1 );
                if ( is_okay ( i , j-1 , M ) )
                    g.add_side ( k , k-1 );
                if (j < 4-1 && is_okay ( i+1 , j , M ) )
                    g.add_side ( k , k+4 );
                if ( i > 0 && is_okay ( i-1 , j , M ) )
                    g.add_side ( k , k-4 );
            }
            if( M[i][j] == 1 )
                source = k ;
            if (M[i][j] == 2)
                dest = k;
            k++;
        }
    }
    return g.search (source, dest) ;
}

int main(){
    int M[4][4] = { { 0 , 3 , 0 , 1 }, { 3 , 0 , 3 , 3 }, { 2 , 3 , 0 , 3 },{ 0 , 0 , 3 , 0 }};
    (find(M) == true) ?
    cout << "Possible" : cout << "Not Possible" <<endl ;
    return 0;
}

出力結果

Not Possible

コードの解説

上記の例では、4×4のマトリックスに対して処理を行っています。関数find()では、まず各セルに番号kを割り当てながら、通行可能な隣接セルとの間に辺を張っていきます。セルの値が1ならソース、2ならデスティネーションとして記録します。

補助関数is_okay()は、指定された座標がマトリックスの範囲内であり、かつ壁（値0）でないことを確認します。これにより、範囲外アクセスや壁の通過を防いでいます。

最後に、クラスuse_graphのsearch()メソッドがBFSを実行します。キューを使って頂点を順に処理し、デスティネーションに到達した時点でtrueを返します。キューが空になっても到達できなければ、パスは存在しないと判断されfalseが返されます。

計算量

• 時間計算量： O(N × M) — N×Mのマトリックスの全セルを一度ずつ処理するため
• 空間計算量： O(N × M) — グラフの隣接リストと訪問済みフラグの保存に必要

この手法はBFSを使用しているため、最短経路の探索にも応用できます。また、DFS（深さ優先探索）やUnion-Find（素集合データ構造）を使っても同様の問題を解くことができます。