迷宫中的老鼠问题是众所周知的回溯问题之一。在这里我们将看到这个问题几乎没有变化。假设给定一个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 if
end
登录后复制
示例
#include
#define N 4
using namespace std;
void dispSolution(int sol[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout
