C++で地雷を含むマップ上の最短安全ルートを探索するアルゴリズム

問題の概要

この問題では、二次元配列 mat[][] が与えられます。この配列は経路を表しており、値が 0 のセルは地雷(危険地帯)を示します。目的は、地雷を避けながらスタート地点からゴール地点まで到達できる最短の安全ルートを見つけることです。

安全に移動するためには、地雷の隣接セル(上下左右)も「危険」とみなし、踏まないようにしなければなりません。

移動中に許可される有効な移動は以下の4方向です。

- 左   : mat[i][j] => mat[i-1][j]
- 右   : mat[i][j] => mat[i+1][j]
- 上   : mat[i][j] => mat[i][j-1]
- 下   : mat[i][j] => mat[i][j+1]

入出力の例

入力

mat[][] = {
    {1, 1, 0, 1},
    {1, 1, 0, 1},
    {1, 1, 1, 1},
    {1, 1, 1, 1}
}

出力

最短安全ルートの長さは 7

解説

太字で示したセルを通るのが最適な経路です。

{
    {1, 1, 0, 1},
    {1, 1, 0, 1},
    {1, 1, 1, 1},
    {1, 1, 1, 1}
}

解法アプローチ1:バックトラッキング

まずシンプルな解法としてバックトラッキング(深さ優先探索)を使う方法があります。手順は以下の通りです。

• ステップ1: パスを探索する前に、地雷に隣接するすべてのセルを「危険セル」としてマークします。
• ステップ2: 左端の列にある安全なセルをそれぞれスタート地点として選び、そこから移動を開始します。
• ステップ3: 各移動先が右端の列(ゴール)に到達できるかを確認します。
• ステップ4: ゴールに到達できるすべての経路の中から最短のものを求め、その長さを返します。
• ステップ5: 到達可能な経路が存在しない場合は -1 を返します。

C++での実装例(バックトラッキング)

#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
bool isSafe(int mat[R][C], int isvisited[R][C], int x, int y){
    if (mat[x][y] == 0 || isvisited[x][y])
        return false;
    return true;
}
bool isValid(int x, int y){
    if (x < R && y < C && x >= 0 && y >= 0)
        return true;
    return false;
}
void unSafeCellsInPath(int mat[R][C]){
    for (int i = 0; i < R; i++){
        for (int j = 0; j < C; j++){
            if (mat[i][j] == 0){
                for (int k = 0; k < 4; k++)
                    if (isValid(i + rowNum[k], j + colNum[k]))
                        mat[i + rowNum[k]][j + colNum[k]] = -1;
            }
        }
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++){
            if (mat[i][j] == -1)
                mat[i][j] = 0;
        }
    }
}
void findShortestSafeRouteRec(int mat[R][C], int isvisited[R][C], int i, int j, int &min_dist, int dist){
    if (j == C-1){
        min_dist = min(dist, min_dist);
        return;
    }
    if (dist > min_dist)
        return;
    isvisited[i][j] = 1;
    for (int k = 0; k < 4; k++){
        if (isValid(i + rowNum[k], j + colNum[k]) && isSafe(mat, isvisited, i + rowNum[k], j + colNum[k])){
            findShortestSafeRouteRec(mat, isvisited, i + rowNum[k], j + colNum[k], min_dist, dist + 1);
        }
    }
    isvisited[i][j] = 0;
}
int findShortestSafeRoute(int mat[R][C]){
    int minSafeDist = INT_MAX;
    int isvisited[R][C];
    unSafeCellsInPath(mat);
    for (int i = 0; i < R; i++) {
        if (mat[i][0] == 1) {
            memset(isvisited, 0, sizeof isvisited);
            findShortestSafeRouteRec(mat, isvisited, i, 0, minSafeDist, 0);
            if(minSafeDist == C - 1)
                break;
        }
    }
    if (minSafeDist != INT_MAX)
        return minSafeDist;
    else
        return -1;
}
int main() {
    int mat[R][C] =
    {
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
        { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
    };
    int pathLen = findShortestSafeRoute(mat);
    if(pathLen == -1)
        cout<<"No Safe Path from source to destination possible!";
    else
        cout<<"Shortest Safe route Length is "<<pathLen;
    return 0;
}

出力

Shortest Safe route Length is 10

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

より効率的な別の解法として幅優先探索(BFS)があります。BFSではキューを使って左端の列から順にレベルごとに探索を進めるため、最短距離を自然に求められます。

• ステップ1: 地雷に隣接するセルをすべて危険セル(0)としてマークします。
• ステップ2: 左端の列にある安全なセルをすべてキューに登録し、初期状態とします。
• ステップ3: キューが空になるまで、各セルから上下左右へ展開しながら訪問済み距離を記録します。
• ステップ4: 右端の列に到達した時点の最小距離を答えとして返します。到達できない場合は -1 を返します。

C++での実装例(BFS)

#include <bits/stdc++.h>
using namespace std;
#define R 11
#define C 10
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
struct Key{
    int x,y;
    Key(int i,int j){ x=i;y=j;};
};
bool isValid(int x, int y) {
    if (x < R && y < C && x >= 0 && y >= 0)
        return true;
    return false;
}
int findShortestSafeRoute(int mat[R][C]){
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (mat[i][j] == 0) {
                for (int k = 0; k < 4; k++)
                    if (isValid(i + rowNum[k], j + colNum[k]))
                        mat[i + rowNum[k]][j + colNum[k]] = -1;
            }
        }
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (mat[i][j] == -1)
                mat[i][j] = 0;
        }
    }
    int visited[R][C];
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++)
            visited[i][j] = -1;
    }
    queue<Key> distQueue;
    for(int i=0;i<R;i++){
        if(mat[i][0] == 1){
            distQueue.push(Key(i,0));
            visited[i][0] = 0;
        }
    }
    while(!distQueue.empty()){
        Key k = distQueue.front();
        distQueue.pop();
        int d = visited[k.x][k.y];
        int x = k.x;
        int y = k.y;
        for (int k = 0; k < 4; k++) {
            int xp = x + rowNum[k];
            int yp = y + colNum[k];
            if(isValid(xp,yp) && visited[xp][yp] == -1 && mat[xp][yp] == 1){
                visited[xp][yp] = d+1;
                distQueue.push(Key(xp,yp));
            }
        }
    }
    int pathLen = INT_MAX;
    for(int i=0;i<R;i++){
        if(mat[i][C-1] == 1 && visited[i][C-1] != -1){
            pathLen = min(pathLen,visited[i][C-1]);
        }
    }
    if(pathLen == INT_MAX)
        return -1;
    else
        return pathLen;
}
int main() {
    int mat[R][C] =
    {
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 },
        { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 },
        { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }
    };
    int pathLen = findShortestSafeRoute(mat);
    if(pathLen == -1)
        cout<<"No Safe Path from source to destination possible!";
    else
        cout<<"Shortest Safe route Length is "<<pathLen;
    return 0;
}

出力

Shortest Safe route Length is 10

まとめ

本記事では、地雷を含むグリッド上で最短の安全ルートを求める2つのアルゴリズムを紹介しました。バックトラッキングは直感的に理解しやすい一方で、計算量が増大しやすいという弱点があります。対してBFSは重みなしグラフにおける最短経路問題に最適であり、実務的にも推奨されるアプローチです。どちらの手法でも共通するポイントは、探索前に地雷の周囲を事前に危険セルとしてマークしておくことであり、これにより探索範囲を大幅に絞り込めます。