• 日期: 2025-10-15
  • 标签: 常规

C++迷宫最短路径算法实现及优化

在编程中，迷宫问题是一个经典的搜索问题，其目标是在一个由障碍物和通路组成的迷宫中找到从起点到终点的最短路径。解决迷宫问题常用的算法有深度优先搜索（DFS）和广度优先搜索（BFS）。本文将介绍这两种算法的C++实现，并解决一个DFS算法中输出路径包含起点坐标的错误。

1. 深度优先搜索（DFS）

DFS 算法是一种递归算法，它从起点开始，沿着一个方向尽可能深地探索，直到找到终点或到达无法继续前进的位置。如果当前路径无法到达终点，DFS 算法会回溯到上一个节点，并尝试其他方向。

算法步骤：

  1. 将起点压入栈中，并标记起点已访问。2. 当栈不为空时，执行以下步骤： * 弹出栈顶元素，获取当前节点的坐标。 * 如果当前节点是终点，则找到了一条路径，返回 true。 * 遍历当前节点的四个相邻节点，如果相邻节点有效且未访问： * 将相邻节点压入栈中。 * 标记相邻节点已访问。 * 递归调用 DFS 函数，如果找到路径则返回 true。3. 如果遍历完所有节点仍未找到路径，则返回 false。

**代码实现：**cpp#include #include #include 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 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) {            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 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) {            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 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;

    // 修正错误：判断栈是否为空，避免输出起点坐标        if (x == start_x && y == start_y && s.empty()) {             break;        }

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

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

        if (isValid(new_x, new_y)) {                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)) {            printPath(start_x, start_y, end_x, end_y);            cout << endl;        } else {            // 使用队列找最短路径            if (findShortestPathBFS(start_x, start_y, end_x, end_y)) {                printPath(start_x, start_y, end_x, end_y);                cout << endl;            } else {                cout << '没有通路' << endl;            }        }    }

return 0;}

错误修正:

在 printPath 函数中，当找到起点时，栈中仍然包含起点的坐标。因此，需要在打印路径时判断栈是否为空，以避免输出起点的坐标。具体来说，将 if (x == start_x && y == start_y) 条件改为 if (x == start_x && y == start_y && s.empty()) 即可。

2. 广度优先搜索（BFS）

BFS 算法是一种层序遍历算法，它从起点开始，逐层向外扩展，直到找到终点。BFS 算法使用队列来存储待访问的节点，并保证先访问的节点距离起点更近。

算法步骤：

  1. 将起点入队，并标记起点已访问。2. 当队列不为空时，执行以下步骤： * 队首元素出队，获取当前节点的坐标。 * 如果当前节点是终点，则找到了一条路径，返回 true。 * 遍历当前节点的四个相邻节点，如果相邻节点有效且未访问： * 将相邻节点入队。 * 标记相邻节点已访问。3. 如果遍历完所有节点仍未找到路径，则返回 false。

**代码实现：**cpp// ... (其他代码与 DFS 相同)

// 使用队列确定最短路径bool findShortestPathBFS(int start_x, int start_y, int end_x, int end_y) { queue 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) {            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;}

// ... (其他代码与 DFS 相同)

3. 测试

输入以下迷宫数据：

4 51 0 0 0 01 1 1 0 11 0 0 1 11 1 1 1 1

程序输出：

(1,1,0),(2,1,0),(2,2,0),(2,3,0),(3,3,0),(4,3,0),(4,4,0),(4,5,0)

这表明程序找到了从起点 (1, 1) 到终点 (4, 5) 的最短路径。

总结

本文介绍了使用 C++ 实现迷宫最短路径算法的两种方法：DFS 和 BFS。同时，我们也解决了一个 DFS 算法中输出路径包含起点坐标的错误。在实际应用中，我们可以根据具体情况选择合适的算法来解决迷宫问题。

C++迷宫最短路径算法实现及优化

原文地址: http://www.cveoy.top/t/topic/XTM 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录