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

上述代码的说明

在上述方法中，我们检查它可以从当前单元格生成的每条路径，在检查时，我们现在将路径标记为一条。当我们的路径到达死胡同时，我们检查该死胡同是否是我们的目的地。现在，如果那不是我们的目的地，我们就回溯，当我们回溯时，我们将单元格标记为 0，因为该路径无效，这就是我们的代码的处理方式。

结论

在本教程中，我们将解决迷宫中的老鼠问题，允许多个步骤或跳跃。我们还学习了该问题的 C++ 程序以及解决该问题的完整方法（普通）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望本教程对您有所帮助。

以上是C++ 允许多步或跳跃的迷宫中的老鼠的详细内容。更多信息请关注PHP中文网其他相关文章！