C++解决生活中的算法：走迷宫

谢士广博客 02-28 阅读 98评论

一、问题

给出一个矩阵（表示迷宫），由n行m列组成，每个元素只能是0或者1，0表示死路，1表示通路，求出一条从左上角走到右下角的可能的路线，并输出其长度。

例如：

已知迷宫图1，可以行走的路线为图2。

$egin{bmatrix} 1 & 1 & 1 \ 0 & 1 & 0 \ 0 & 1 & 1 \ end{bmatrix}$ $egin{bmatrix} extcolor{red}{mathbf{1}} & extcolor{red}{mathbf{1}} & 1 \ 0 & extcolor{red}{mathbf{1}} & 0 \ 0 & extcolor{red}{mathbf{1}} & extcolor{red}{mathbf{1}} \ end{bmatrix}$

图1 图2

二、实现

首先，我们先将框架搭建好。

#include using namespace std;int n, m;int maze[105][105];int main(){ cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> maze[i][j]; } } printMinLength(n, m, maze); return 0;}

然后，我们拼接出函数。

#include using namespace std;int n, m;int maze[105][105];bool isRoad(int x, int y); // 是不是通路bool go(int &x, int &y); // 向前试探1步void printMinLength(int n, int m, int maze[][105]); // 输出最短路径长度int main(){ cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> maze[i][j]; } } printMinLength(n, m, maze); return 0;}bool isRoad(int x, int y){ // 情况1: 越界 if (x < 1 || y < 1) return false; if (x > n || y > m) return false; // 情况2: 在矩阵内死路 if (maze[x][y] == 0) return false; // 情况3: 在矩阵内通路 return true;}bool go(int &x, int &y){ if (isRoad(x + 1, y)) // 向下走是通路 { x++; return true; } else if (isRoad(x, y + 1)) // 向右走是通路 { y++; return true; } else if (isRoad(x - 1, y)) // 向上是通路 { x--; // 回溯到上一步 return true; } else if (isRoad(x, y - 1)) // 向左是通路 { y--; return true; } else { return false; // 四个方向都不通，迷宫无解 }}void printMinLength(int n, int m, int maze[][105]){ int x = 1, y = 1; while (true) { cout << x << "," << y << " -> "; if (!go(x, y)) { cout << "迷宫无解" << endl; break; } if (x == n && y == m) { cout << n << "," << m << endl << "抵达终点! "; break; } }}

最后，我们来运行一下。

INPUT5 51 1 1 1 10 0 0 0 10 1 0 0 10 1 0 1 10 1 0 0 1CORRECT OUTPUT1,1 -> 1,2 -> 1,3 -> 1,4 -> 1,5 -> 2,5 -> 3,5 -> 4,5 -> 5,5抵达终点! MY OUTPUT1,1 -> 1,2 -> 1,3 -> 1,4 -> 1,5 -> 2,5 -> 3,5 -> 4,5 -> 5,5抵达终点!

但是无解的时候，就会开始反复横跳……

不过，只要不是无解，这个程序就可以啦！