C++ 迷宫中的老鼠，允许多次行走或跳跃
c++server side programmingprogramming
给定一个 n*n 网格迷宫。我们的老鼠位于网格的左上角。现在老鼠只能向下或向前移动，并且当且仅当方块具有非零值时，现在在此变体中老鼠才允许多次跳跃。老鼠从当前单元格可以进行的最大跳跃高度是单元格中存在的数字，现在您的任务是确定老鼠是否可以到达网格的右下角，例如 −
输入:{ { {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，然后打印该路径。否则，我们打印该路径不存在。
示例
#include <bits/stdc++.h>
using namespace std;
#define N 4 // 网格的大小
bool resolveMaze(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; // 我们将此索引作为路径包含在内
for (int i = 1; i <= maze[x][y] && i < N; i++) { // 因为 maze[x][y] 表示您可以进行的跳跃次数 //所以我们检查每个方向的每次跳跃
if (solveMaze(maze, x + i, y, sol) == true) // 向右跳跃
return true;
if (solveMaze(maze, x, y + i, sol) == true) // 向下跳跃
return true;
}
sol[x][y] = 0; // 如果没有一个为真，则路径不存在
//或者路径中不包含当前单元格
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
上述代码的解释
在上述方法中，我们检查从当前单元格可以生成的每条路径，在检查的同时，我们将这些路径标记为一条。当我们的路径到达死胡同时，我们会检查该死胡同是否是我们的目的地。现在，如果那不是我们的目的地，我们会回溯，在回溯时，我们将单元格标记为 0，因为这条路径无效，这就是我们的代码的执行方式。
结论
在本教程中，我们解决了允许多个步骤或跳跃的迷宫中的老鼠问题。我们还学习了这个问题的 C++ 程序以及我们解决这个问题的完整方法(正常)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。我们希望您觉得本教程有用。
