C++で解く複数ジャンプが可能な迷路のネズミ問題（Rat in a Maze）

問題の概要

n×n のグリッド状の迷路が与えられ、ネズミはグリッドの左上のマスからスタートします。ネズミは「下」または「右」にのみ移動でき、さらに移動先のマスが 0 以外の値を持つ場合にのみ進むことができます。この問題のバリエーションでは、ネズミは複数マスのジャンプが許されており、現在のマスからジャンプできる最大距離はそのマスに書かれた数値です。ネズミがグリッドの右下のマスに到達できるかどうかを判定するのが課題です。

以下に入力と出力の例を示します。

入力 :
{{1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}}

出力 :
{{1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}}

入力 :
{{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}}

出力 : 経路は存在しません

解法のアプローチ：バックトラッキング

このアプローチでは、バックトラッキング（探索の巻き戻し）を用いて、ネズミが辿れるすべての経路を追跡します。いずれかの経路でネズミが目的地に到達できた場合は、その経路について true を返し、経路を出力します。どの経路でも到達できなかった場合は、「経路が存在しない」ことを出力します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define N 4 // グリッドのサイズ

// 経路を探索する再帰関数
bool solveMaze(int maze[N][N], int x, int y, int sol[N][N]){
    if (x == N - 1 && y == N - 1) { // ゴールに到達したら true を返し、ゴールを 1 でマーク
        sol[x][y] = 1;
        return true;
    }
    if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
        sol[x][y] = 1; // このマスを経路に含める
        // maze[x][y] はジャンプできる最大回数を表すため、
        // 各方向についてすべてのジャンプ数を試します
        for (int i = 1; i <= maze[x][y] && i < N; i++) {
            if (solveMaze(maze, x + i, y, sol) == true) // 右へジャンプ
                return true;
            if (solveMaze(maze, x, y + i, sol) == true) // 下へジャンプ
                return true;
        }
        sol[x][y] = 0; // どれも true でなければ、その経路は存在しない
                       // （または現在のマスは経路に含まれない）
        return false;
    }
    return false;
}
int main(){
    int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 },{ 0, 1, 0, 1 },
                       { 0, 0, 0, 1 } };
    int sol[N][N];
    memset(sol, 0, sizeof(sol));
    if(solveMaze(maze, 0, 0, sol)){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++)
                cout << sol[i][j] << " ";
            cout << "\n";
        }
    }
    else
        cout << "Path doesn't exist\n";
    return 0;
}

出力結果

1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1

コードの解説

このアプローチでは、現在のマスから辿れるすべての経路を確認し、その過程で通過したマスを 1 としてマークしていきます。経路が行き止まりに達したら、その行き止まりが目的地かどうかを判定します。目的地でない場合はバックトラッキングを行い、巻き戻す際にその経路が有効ではないため、該当するマスを 0 に戻します。この処理を繰り返すことで、コードは正しい経路を探索していきます。

まとめ

このチュートリアルでは、複数のステップ（ジャンプ）が許可された「迷路のネズミ」問題を解きました。この問題に対する C++ プログラムと、それを解くための標準的なアプローチについても学びました。同じプログラムは、C、Java、Python などの他の言語でも実装できます。本チュートリアルが皆さんのお役に立てば幸いです。