|
之前我们讨论了迷宫中的老鼠的例子。现在我们改变老鼠走迷宫的条件，允许老鼠一次走多个格子。 我们用下面的例子来描述新的老鼠走迷宫的问题。 上图是一个N * N 二维矩阵形状的迷宫（矩阵简称为M），有一只老鼠从左上角的单元格，即M [0] [0]出发，试图走到右下角的出口，即M[N-1][N-1]。灰色的方格表示死胡同，不允许老鼠进入。老鼠可以向下或向右移动。与上一题不同的是，现在允许老鼠每次移动一个或多个格子，但是允许移动的格子数是有规定的，具体规定由下面的矩阵来描述。 上面的矩阵指定了从每个方格M[i][j]（0≤i≤N-1,0≤j≤N-1）中，大鼠可以向右移动多个格子（例如：到M[i][j+s]），或向下的若干格子（例如：到M [i+s][j]），其中最大步数（或s的最大值）由单元格中的值M[i][j]来限定。如果任何方格包含0，那么这是一个死胡同。例如：M[0][0]的值是2，表示老鼠最多一次可以跳转2步，它可以从M[0][0]跳转到以下任何一个方格：M[0][1]，M[0][2]，M[1][0]或M[2][0]。但由于单元格M[1][0]的值是0，死胡同，实际上老鼠不能进入该单元格，所以老鼠实际可以从M[0][0]跳转到的有效单元方格是：M[0][1]，M[0][2]或M[2][0]。 上面例子的一个可能的路径如下图所示。 如果用大小为N * N的矩阵的形式打印从老鼠M[0][0]跳跃到M[N-1][N-1]的可能路径，并且使处于路径中的所有单元格的值为1，而不在路径中的其他单元格的值为0。那么上面例子的对应路径如下图所示。 【思考题】 老鼠迷宫对应的矩阵如下，请您依照上面描述的规则找出老鼠走出迷宫的路径并以矩阵形式输出。 输入：mat[][] = { {3, 0, 0, 2, 1}, {0, 0, 0, 0, 2}, {0, 1, 0, 1, 0}, {1, 0, 0, 1, 1}, {3, 0, 0, 1, 1} } 算法思路 我们再定义一个矩阵CRF[N][N]，记录是否可以从元素对应的位置出发到达出口。矩阵元素CRF[i][j]的值都是布尔值，要么是true，要么是false。 如果某个矩阵元素CRF[i][j]的值为true，表示由此出发，至少有一条符合条件的路径可以到达出口。反之，若某个矩阵元素CRF[i][j]的值为false，表示由此出发，找不到任何符合条件的路径可以到达出口。 先将矩阵CRF进行初始化，开始使CRF[N-1][N-1] 的值为true，因为已经在出口，当然能直接到达出口。而将布尔矩阵CRF[N][N]的其他位置的元素都设置为false。 我们的策略是从出口开始，逐步更新布尔矩阵CRF中的每个对应元素值，使它能正确表示是否能由此出发到达出口：
代码实现 下面是用C++代码的上述算法。 #include <iostream> using namespace std; #define MAX 50 //检查是否存在通路的函数 //矩阵maze存放原始迷宫的初始条件 //矩阵sol存放找到的解——走出迷宫的路径 bool hasPath(int maze[][MAX], int sol[][MAX], int N) { //初始化解决方案路径 for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) sol[i][j] = 0; //声明并初始化CRF矩阵 bool** CRF = new bool*[N]; for (int i = 0; i < N; i++) CRF[i] = new bool[N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) CRF[i][j] = false; CRF[N - 1][N - 1] = true; //使用动态编程方法填充CRF矩阵的值 for (int k = N - 1; k >= 0; k--) { for (int j = k; j >= 0; j--) { if (!(k == N - 1 && j == N - 1)) { // 是否可以从maze[k][j]位置达到一个有效的位置 for (int a = 0; a <= maze[k][j]; a++) { if ((j + a < N && CRF[k][j + a] == true) || (k + a < N && CRF[k + a][j] == true)) { CRF[k][j] = true; break; } } // 是否可以从maze[j][k]位置达到一个有效的位置 for (int a = 0; a <= maze[j][k]; a++) { if ((k + a < N && CRF[j][k + a] == true) || (j + a < N && CRF[j + a][k] == true)) { CRF[j][k] = true; break; } } } } } //下面的程序是依据矩阵CRF的值，找到记录老鼠走出迷宫的路径的矩阵sol //如果 CRF[0][0] 是false, 表示我们根本无法从出口到达迷宫的出口，直接返回 if (CRF[0][0] == false) return false; //基于CRF找到包含解的sol矩阵 int i = 0, j = 0; while (!(i == N - 1 && j == N - 1)) { sol[i][j] = 1; if (maze[i][j] > 0) //从当前位置移动到下一个可以达到的位置 for (int a = 1; a <= maze[i][j]; a++) { if ((j + a < N && CRF[i][j + a] == true)) { j = j + a; break; } else if ((i + a < N && CRF[i + a][j] == true)) { i = i + a; break; } } } sol[N - 1][N - 1] = 1; return true; } //打印输出包含路径的矩阵 void printMatrix(int sol[][MAX], int N) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << sol[i][j] << ' '; cout << '\n'; } } // 主程序 int main() { int maze[][MAX] = { { 2, 2, 1, 1, 0 }, { 0, 0, 3, 0, 0 }, { 1, 0, 0, 0, 0 }, { 0, 0, 2, 0, 1 }, { 0, 0, 3, 0, 0 } }; int N = sizeof(maze) / sizeof(maze[0]); int sol[N][MAX]; // 如有存在路径 if (hasPath(maze, sol, N)) // 打印输出路径 printMatrix(sol, N); else cout << 'No path exists'; return 0; } 请你运行上述代码，看看是否能得到下面的正确答案。 练习题 请您针对对本节课开始提出的思考题，找到正确的答案并输出。 点击原文可以查看部分老鼠走迷宫的动画课件。 |
|
|
