本文共 2564 字，大约阅读时间需要 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/