C++ 迷宫中的老鼠,允许多步或跳跃
给定一个*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 //我们网格的大小 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; //我们将此索引作为路径包含在内 for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take //所以我们检查每个方向的每一次跳跃 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++程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序,例如C、java、python和其他语言。我们希望本教程对您有所帮助。