複数のステップまたはジャンプを可能にする迷路内の C++ ラット

n*n グリッドの迷路があるとします。マウスがグリッドの左上隅に表示されます。マウスは下または前にのみ移動できるようになり、このバリアントでは、ブロックがゼロ以外の値を持つ場合に限り、マウスは複数のジャンプを行うことができます。マウスが現在のセルから実行できる最大ジャンプは、セル内に存在する数値です。ここでのタスクは、マウスがグリッドの右下隅に到達できるかどうかを確認することです。たとえば、

Input : { { {1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}
},
Output : { {1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}
}

Input : {
{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}
}
Output: Path doesn't exist

解決策を見つける方法

このアプローチでは、バックトラッキングを使用して、マウスが現在たどることができるすべてのパスを追跡します。マウスがいずれかのパスから目的地に到達した場合、そのパスに対して true を返し、そのパスを出力します。それ以外の場合は、パスが存在しないことが出力されます。

例

 
#include <bits/stdc++.h>
using namespace std;
#define N 4 // size of our grid
bool solveMaze(int maze[N][N], int x, int y, // recursive function for finding the path
    int sol[N][N]){
        if (x == N - 1 && y == N - 1) { // if we reached our goal we return true and mark our goal as 1
            sol[x][y] = 1;
            return true;
    }
    if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
        sol[x][y] = 1; // we include this index as a path
        for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take                                             //so we check for every jump in every direction
            if (solveMaze(maze, x + i, y, sol) == true) // jumping right
               return true;
            if (solveMaze(maze, x, y + i, sol) == true) // jumping downward
               return true;
        }
        sol[x][y] = 0; // if none are true then the path doesn&#39;t exist
                   //or the path doesn&#39;t contain current cell in it
        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&#39;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 などの他の言語で書くことができます。このチュートリアルがお役に立てば幸いです。

以上が複数のステップまたはジャンプを可能にする迷路内の C++ ラットの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。