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

一、问题

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

        例如：

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

图1                                                 图2

二、实现

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

#include using namespace std;int n, m;int maze[105][105];int main(){    cin >> n >> m;    for (int i = 1; i  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  maze[i][j];        }    }    printMinLength(n, m, maze);    return 0;}bool isRoad(int x, int y){    // 情况1: 越界    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  1,3 -> 1,4 -> 1,5 -> 2,5 -> 3,5 -> 4,5 -> 5,5抵达终点! 

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

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