
给定一个 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>
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 <h2>输出</h2>
<pre class="brush:php;toolbar:false;">1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1
上述代码的说明
在上述方法中,我们检查它可以从当前单元格生成的每条路径,在检查时,我们现在将路径标记为一条。当我们的路径到达死胡同时,我们检查该死胡同是否是我们的目的地。现在,如果那不是我们的目的地,我们就回溯,当我们回溯时,我们将单元格标记为 0,因为该路径无效,这就是我们的代码的处理方式。
结论
在本教程中,我们将解决迷宫中的老鼠问题,允许多个步骤或跳跃。我们还学习了该问题的 C++ 程序以及解决该问题的完整方法(普通)。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望本教程对您有所帮助。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!










