C++ 迷宫求解算法：使用栈和队列寻找最短路径

本文将介绍使用 C++ 编程语言实现迷宫求解算法，并对比使用栈和队列两种方法寻找最短路径的优缺点。

算法实现

以下是 C++ 代码，展示了使用栈和队列两种方法寻找迷宫最短路径的实现：

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

struct Node {
    int x, y, dir;
    Node(int _x, int _y, int _dir) : x(_x), y(_y), dir(_dir) {}
};

// 定义方向常量
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
const int UP = 4;

// 定义迷宫和访问矩阵
int maze[101][101];
bool visited[101][101];

// 定义移动方向数组
int dx[5] = {0, 1, 0, -1, 0};
int dy[5] = {0, 0, 1, 0, -1};

// 定义迷宫的行数和列数
int M, N;

// 判断坐标是否有效
bool isValid(int x, int y) {
    return x >= 1 && x <= M && y >= 1 && y <= N && maze[x][y] == 1 && !visited[x][y];
}

// 使用栈寻找最短路径
bool findShortestPath(int start_x, int start_y, int end_x, int end_y) {
    stack<Node> s;
    s.push(Node(start_x, start_y, 0));
    visited[start_x][start_y] = true;

    while (!s.empty()) {
        Node currentNode = s.top();
        s.pop();

        int x = currentNode.x;
        int y = currentNode.y;
        int dir = currentNode.dir;

        if (x == end_x && y == end_y) {
            printPath(start_x, start_y, end_x, end_y);
            return true;
        }

        for (int i = dir + 1; i <= 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (isValid(new_x, new_y)) {
                visited[new_x][new_y] = true;
                s.push(Node(new_x, new_y, 0));
                break;
            }
        }
    }

    return false;
}

// 使用队列确定最短路径
bool findShortestPathBFS(int start_x, int start_y, int end_x, int end_y) {
    queue<Node> q;
    q.push(Node(start_x, start_y, 0));
    visited[start_x][start_y] = true;

    while (!q.empty()) {
        Node currentNode = q.front();
        q.pop();

        int x = currentNode.x;
        int y = currentNode.y;
        int dir = currentNode.dir;

        if (x == end_x && y == end_y) {
            printPath(start_x, start_y, end_x, end_y);
            return true;
        }

        for (int i = 1; i <= 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (isValid(new_x, new_y)) {
                visited[new_x][new_y] = true;
                q.push(Node(new_x, new_y, 0));
            }
        }
    }

    return false;
}

// 输出路径
void printPath(int start_x, int start_y, int end_x, int end_y) {
    stack<Node> s;
    s.push(Node(end_x, end_y, 0));

    while (!s.empty()) {
        Node currentNode = s.top();
        s.pop();

        int x = currentNode.x;
        int y = currentNode.y;
        int dir = currentNode.dir;

        cout << '(' << x << ',' << y << ',' << dir << ')';
        if (s.size() % 5 == 0) {
            cout << endl;
        } else if (!s.empty()) {
            cout << ',';
        }

        for (int i = 1; i <= 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (isValid(new_x, new_y)) {
                visited[new_x][new_y] = true;
                s.push(Node(new_x, new_y, i));
                break;
            }
        }
    }
}

int main() {
    while (cin >> M >> N && M != 0 && N != 0) {
        // 初始化迷宫和访问矩阵
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                cin >> maze[i][j];
                visited[i][j] = false;
            }
        }

        int start_x = 1, start_y = 1;
        int end_x = M, end_y = N;

        // 使用栈找最短路径
        if (findShortestPath(start_x, start_y, end_x, end_y)) {
            cout << endl;
        } else {
            // 使用队列找最短路径
            if (findShortestPathBFS(start_x, start_y, end_x, end_y)) {
                cout << endl;
            } else {
                cout << '没有通路' << endl;
            }
        }
    }

    return 0;
}

代码分析

数据结构定义
- Node 结构体表示迷宫中的一个节点，包含坐标 x 和 y 以及到达该节点的方向 dir。
- maze 数组表示迷宫地图，1 代表可通行路径，0 代表墙壁。
- visited 数组记录已经访问过的节点，防止重复访问。
- dx 和 dy 数组分别表示四个方向的横向和纵向偏移量。
isValid 函数
- 判断一个节点是否有效，即该节点是否在迷宫范围内、是否可通行以及是否已经被访问过。
findShortestPath 函数 (使用栈)
- 使用栈来实现深度优先搜索 (DFS)。
- 从起点开始，将起点入栈并标记为已访问。
- 循环遍历栈，取出栈顶节点，并依次尝试四个方向的移动。
- 如果目标节点被找到，则打印路径并返回 true。
findShortestPathBFS 函数 (使用队列)
- 使用队列来实现广度优先搜索 (BFS)。
- 从起点开始，将起点入队并标记为已访问。
- 循环遍历队列，取出队首节点，并依次尝试四个方向的移动。
- 如果目标节点被找到，则打印路径并返回 true。
printPath 函数
- 使用栈来存储路径信息。
- 从终点开始，将终点入栈，并循环遍历栈，将路径信息输出。

总结

使用栈实现深度优先搜索，可以找到一条从起点到终点的路径，但可能不是最短路径。
使用队列实现广度优先搜索，可以找到从起点到终点的最短路径。
两种方法各有优缺点，根据实际需求选择合适的方法。

优化建议

可以使用更简洁的数据结构来表示迷宫，例如使用一个二维数组来表示迷宫，每个元素代表一个节点，并使用一个枚举类型来表示节点的状态（墙壁、空地、起点、终点）。
可以优化路径打印算法，例如使用一个数组来存储路径，并使用一个指针指向当前节点，这样就可以避免使用栈来存储路径信息。
可以使用更高效的搜索算法，例如 A* 算法，可以更快地找到最短路径。

代码示例

// 输入迷宫数据
int maze[101][101] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 1, 0},
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 1, 0},
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

// 迷宫大小
int M = 7, N = 10;

// 主函数
int main() {
    // 使用栈寻找最短路径
    if (findShortestPath(1, 1, M, N)) {
        cout << '使用栈找到最短路径：' << endl;
    } else {
        cout << '使用栈没有找到路径！' << endl;
    }

    // 使用队列寻找最短路径
    if (findShortestPathBFS(1, 1, M, N)) {
        cout << '使用队列找到最短路径：' << endl;
    } else {
        cout << '使用队列没有找到路径！' << endl;
    }

    return 0;
}

希望本文能够帮助您理解迷宫求解算法，并能够应用于实际项目中。