C++ 迷宫求解算法：非递归算法及最短路径

以下是一个用 C++ 实现的求解迷宫的非递归程序：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// 定义迷宫的行列数
const int m = 5;
const int n = 5;

// 定义迷宫的通路和障碍
const int maze[m][n] = {
    {1, 0, 1, 1, 1},
    {1, 0, 1, 0, 1},
    {1, 1, 1, 1, 1},
    {1, 0, 0, 0, 1},
    {1, 1, 1, 0, 1}
};

// 定义坐标结构体
struct Point {
    int x;
    int y;
    Point(int _x, int _y) : x(_x), y(_y) {}
};

// 判断坐标是否合法
bool isValid(int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 1;
}

// 求解迷宫的非递归函数
void solveMaze() {
    stack<Point> s;  // 使用栈存储通路
    vector<vector<bool>> visited(m, vector<bool>(n, false));  // 记录访问过的坐标
    vector<vector<Point>> prev(m, vector<Point>(n, Point(-1, -1)));  // 记录每个坐标的前一个坐标

    // 入口坐标
    Point start(0, 0);
    // 出口坐标
    Point end(m-1, n-1);

    // 将入口加入栈中
    s.push(start);
    visited[start.x][start.y] = true;

    while (!s.empty()) {
        Point current = s.top();
        s.pop();

        // 如果到达出口，停止搜索
        if (current.x == end.x && current.y == end.y) {
            break;
        }

        // 上下左右四个方向的坐标偏移
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

        // 搜索上下左右四个方向
        for (int i = 0; i < 4; i++) {
            int nextX = current.x + dx[i];
            int nextY = current.y + dy[i];

            // 如果坐标合法且未被访问过
            if (isValid(nextX, nextY) && !visited[nextX][nextY]) {
                s.push(Point(nextX, nextY));
                visited[nextX][nextY] = true;
                prev[nextX][nextY] = current;
            }
        }
    }

    // 判断是否找到通路
    if (!visited[end.x][end.y]) {
        cout << '迷宫中没有通路' << endl;
    } else {
        // 输出通路坐标
        vector<Point> path;
        Point current = end;
        while (current.x != -1 && current.y != -1) {
            path.push_back(current);
            current = prev[current.x][current.y];
        }
        cout << '迷宫的通路为：' << endl;
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << '(' << path[i].x << ', ' << path[i].y << ')' << endl;
        }
    }
}

int main() {
    solveMaze();
    return 0;
}

这个程序使用了一个栈来存储通路，使用了一个二维数组来记录坐标是否被访问过，使用了另一个二维数组来记录每个坐标的前一个坐标。通过搜索上下左右四个方向来寻找通路，直到找到出口或者栈为空。最后根据前一个坐标数组来输出通路。

对于迷宫中所有可能的通路，并输出最短路径，可以采用广度优先搜索的方法。在上面的代码中，可以将栈改为队列，并将搜索顺序改为广度优先搜索的顺序，最后输出的通路即为最短路径。