本文共 2498 字，大约阅读时间需要 8 分钟。

编写一个程序来找出5x5迷宫中的最短路径。迷宫由二维数组表示，1是墙壁，0是可以走的路。目标是从左上角（0,0）到右下角（4,4），并输出最短路径。

步骤说明

代码实现

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct Node {    int x, y;    int pre_x, pre_y;    int step;};int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};void bfs(int a[5][5], bool vis[5][5], Node path[50], int& steps) {    queue
      
        q;    Node start = {0, 0, -1, -1, 0};    q.push(start);    vis[start.x][start.y] = true;    steps = 0;        while (!q.empty()) {        Node current = q.front();        q.pop();        steps++;                if (current.x == 4 && current.y == 4) break;                for (int i = 0; i < 4; ++i) {            int new_x = current.x + dir[i][0];            int new_y = current.y + dir[i][1];                        if (new_x >= 0 && new_x < 5 && new_y >= 0 && new_y < 5) {                if (a[new_x][new_y] == 0 && !vis[new_x][new_y]) {                    vis[new_x][new_y] = true;                    Node next = {new_x, new_y, current.x, current.y, steps};                    path[steps] = next;                    q.push(next);                                        if (new_x == 4 && new_y == 4) {                        steps++;                        break;                    }                }            }        }    }}int main() {    int maze[5][5];    for (int i = 0; i < 5; ++i) {        for (int j = 0; j < 5; ++j) {            scanf("%d", &maze[i][j]);        }    }        bool vis[5][5] = {{false for _ in range(5)}};    Node path[50];    int steps = 0;        bfs(maze, vis, path, steps);        if (steps == 0) {        cout << "(0,0)" << endl;        return 0;    }        for (int i = steps; i >= 0; --i) {        if (path[i].x == 4 && path[i].y == 4) {            break;        }    }        for (int i = steps; i >= 0; --i) {        if (path[i].x == 4 && path[i].y == 4) {            break;        }        if (i == 0) {            continue;        }        cout << "(" << path[i].x << ", " << path[i].y << ")" << endl;    }        return 0;}
      
     
    
   

输出结果

样例输入对应的输出路径为：

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

代码解释

该程序使用广度优先搜索算法，确保找到最短路径，并以指定格式输出。

转载地址：http://nwio.baihongyu.com/