C++求解迷宫从入口到出口的一条最短路径案例代码

题目描述

求解迷宫从入口到出口的一条最短路径。输入一个迷宫，求从入口通向出口的一条可行最短路径。为简化问题，迷宫用二维数组 int maze[10][10]来存储障碍物的分布，假设迷宫的横向和纵向尺寸的大小是一样的，并由程序运行读入, 若读入迷宫大小的值是n（3<n<=10），则该迷宫横向或纵向尺寸都是n，规定迷宫最外面的一圈是障碍物，迷宫的入口是maze[1][1]，出口是maze[n-2][n-2], 若maze[i][j] = 1代表该位置是障碍物，若maze[i][j] = 0代表该位置是可以行走的空位（0<=i<=n-1, 0<=j<=n-1）。求从入口maze[1][1]到出口maze[n-2][n-2]可以走通的路径。

要求迷宫中只允许在水平或上下四个方向的空位上行走，走过的位置不能重复走，规定必须按向右、向下、向左、向上的顺序向前搜索试探，输出先到达出口的最短路径。

案例代码

这个问题可以使用广度优先搜索（BFS）算法来解决。首先，我们需要构建一个辅助的数据结构来保存迷宫中每个位置的状态（是否访问过、路径长度等），然后使用队列来辅助进行广度优先搜索。

具体的实现步骤如下：

1. 定义一个结构体 Point，用于保存每个位置的状态信息，包括坐标和路径长度。
2. 创建一个二维数组 maze 来表示迷宫，并根据输入初始化迷宫。
3. 创建一个二维数组 visited 来记录每个位置是否已经访问过。
4. 创建一个队列 q，用于辅助进行广度优先搜索。
5. 将入口点 (1, 1) 加入队列，并将其设置为已访问。
6. 使用循环，从队列中取出当前位置 (x, y)，并检查是否到达出口 (n-2, n-2)，如果是，则找到最短路径。
7. 否则，依次尝试向右、向下、向左、向上四个方向走，如果下一个位置是可行的并且未访问过，则将其加入队列，并更新其状态信息（坐标和路径长度）。
8. 循环直到队列为空或找到最短路径。
9. 输出最短路径的长度和路径经过的位置。

以下是C++代码实现

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

// 结构体定义每个位置的状态信息
struct Point {
    int x;
    int y;
    int dist;

    Point(int _x, int _y, int _dist) : x(_x), y(_y), dist(_dist) {}
};

int main() {
    int n;
    cout << "请输入迷宫的大小（3<n<=10）：" << endl;
    cin >> n;

    int maze[10][10];
    cout << "请输入迷宫的障碍物分布：" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> maze[i][j];
        }
    }

    // 记录每个位置是否已经访问过
    bool visited[10][10] = {false};

    // 定义四个方向的偏移量
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};

    // 创建队列，并将入口点加入队列
    queue<Point> q;
    q.push(Point(1, 1, 0));
    visited[1][1] = true;

    // 记录最终的最短路径长度
    int shortestPathLength = -1;

    // 广度优先搜索
    while (!q.empty()) {
        Point cur = q.front();
        q.pop();

        // 到达出口，找到最短路径
        if (cur.x == n - 2 && cur.y == n - 2) {
            shortestPathLength = cur.dist;
            break;
        }

        // 依次尝试向右、向下、向左、向上四个方向走
        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            // 如果下一个位置是可行的并且未访问过
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && maze[nx][ny] == 0 && !visited[nx][ny]) {
                q.push(Point(nx, ny, cur.dist + 1));
                visited[nx][ny] = true;
            }
        }
    }

    // 输出结果
    if (shortestPathLength != -1) {
        cout << "最短路径长度为：" << shortestPathLength << endl;
    } else {
        cout << "无法找到可行路径" << endl;
    }

    return 0;
}

用户需要首先输入迷宫的大小（3<n<=10），然后输入迷宫的障碍物分布。程序会进行广度优先搜索，寻找从入口 (1, 1) 到出口 (n-2, n-2) 的最短路径，并输出路径长度。如果无法找到可行路径，则输出提示信息。