迷宫中的老鼠问题是众所周知的回溯问题之一。在这里我们将看到这个问题几乎没有变化。假设给定一个NxN迷宫M。起点为左上角 M[0, 0]，终点为右下角 M[N – 1, N – 1]。一只老鼠被放置在起点。我们的目标是找到一条从起点到终点的路径，可以让老鼠到达目的地。这里老鼠可以跳跃（变体）。现在有一些限制
老鼠可以向右或向下移动。迷宫中单元格中带有 0 表示该单元格是被阻止。非零单元格表示有效路径。单元格内的数字表示大鼠从该单元格可以进行的最大跳跃次数。 ul>
算法
ratInMaze
begin if destination is reached, then print the solution matrix else 1. Place the current cell inside the solution matrix as 1 2. Move forward or jump (check max jump value) and recursively check if move leads to solution or not. 3. If the move taken from the step 2 is not correct, then move down, and check it leads to the solution or not 4. If none of the solutions in step 2 and 3 are correct, then make the current cell 0. end ifend
示例
#include #define N 4using namespace std;void dispSolution(int sol[N][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << sol[i][j] << " "; cout <= 0 && x = 0 && y < N && maze[x][y] != 0) return true; return false;}bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) { if (x == N - 1 && y == N - 1) { //if destination is found, return true sol[x][y] = 1; return true; } if (isSafe(maze, x, y)) { sol[x][y] = 1; //mark 1 into solution matrix for (int i = 1; i <= maze[x][y] && i < N; i++) { if (ratMazeSolve(maze, x + i, y, sol)) //move right return true; if (ratMazeSolve(maze, x, y + i, sol)) //move down return true; } sol[x][y] = 0; //if the solution is not valid, then make it 0 return false; } return false;}bool solveMaze(int maze[N][N]) { int sol[N][N] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; if (!ratMazeSolve(maze, 0, 0, sol)) { cout << "Solution doesn't exist"; return false; } dispSolution(sol); return true;}main() { int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 }, { 0, 1, 0, 1 }, { 0, 0, 0, 1 } }; solveMaze(maze);}
输出
1 0 0 01 0 0 10 0 0 10 0 0 1
以上就是迷宫中的老鼠是否可以进行多步或跳跃？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444015.html
微信扫一扫 
支付宝扫一扫 
