定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 输入 一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。 输出 左上角到右下角的最短路径，格式如样例所示。

样例输入：
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出：
(0, 0)-->(1, 0)-->(2, 0)-->(2, 1)-->(2, 2)-->(1, 2)-->(0, 2)-->(0, 3)-->(0, 4)-->(1, 4)-->(2, 4)-->(3, 4)-->(4, 4)

相关问题

定义一个二维数组：int maze[5][5]={{0,1,0,0,0},{0,1,0,1,0}{0,0,0,0,0}{0,1,1,1,0}{0,0,0,1,0}}它表示一个迷宫其中的1表示墙壁0表示出口写出它从左上角到右下角的最短路径

这道题可以使用广度优先搜索（BFS）来解决。我们从起点开始，一层一层地向外扩展，直到找到终点为止。

首先，我们需要定义一个结构体来表示迷宫中的一个位置，包括该位置的行和列以及到起点的距离。同时，我们需要定义一个队列，用于存储待扩展的位置。

#include <iostream>
#include <queue>

using namespace std;

struct Node {
    int x, y; // 行和列
    int dist; // 到起点的距离
};

int maze[5][5] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}
};

int dx[4] = {-1, 0, 1, 0}; // 上下左右四个方向的行偏移量
int dy[4] = {0, 1, 0, -1}; // 上下左右四个方向的列偏移量

int bfs() {
    queue<Node> q;
    bool vis[5][5] = {false}; // 标记每个位置是否已经访问过
    q.push({0, 0, 0});
    vis[0][0] = true;
    while (!q.empty()) {
        Node curr = q.front();
        q.pop();
        if (curr.x == 4 && curr.y == 4) { // 如果已经到达终点，则返回距离
            return curr.dist;
        }
        for (int i = 0; i < 4; i++) { // 扩展四个方向
            int nx = curr.x + dx[i];
            int ny = curr.y + dy[i];
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && maze[nx][ny] == 0 && !vis[nx][ny]) {
                q.push({nx, ny, curr.dist + 1});
                vis[nx][ny] = true;
            }
        }
    }
    return -1; // 如果无法到达终点，则返回 -1
}

int main() {
    cout << bfs() << endl; // 输出最短路径的长度
    return 0;
}

输出结果为 `8`，表示从左上角到右下角的最短路径长度为 8。

定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

以下是一个可能的解法，使用BFS算法：

#include <iostream>
#include <queue>

using namespace std;

const int N = 5;
int maze[N][N] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0}
};

// 定义一个结构体表示一个点的坐标
struct Point {
int x, y;
};

// 定义一个函数判断一个点是否合法（在迷宫内且没有墙壁）
bool isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0;
}

int bfs(Point start, Point end) {
// 定义一个队列，用于存储待访问的点
queue<Point> q;
// 定义一个二维数组，用于记录每个点是否已经访问过
bool visited[N][N] = {false};
// 定义一个二维数组，用于记录从起点到每个点的距离
int distance[N][N] = {0};
// 将起点加入队列
q.push(start);
visited[start.x][start.y] = true;
distance[start.x][start.y] = 0;
// 定义一个数组表示可以走的四个方向
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
// 开始遍历队列
while (!q.empty()) {
// 取出队首元素
Point p = q.front();
q.pop();
// 如果当前点是终点，直接返回距离
if (p.x == end.x && p.y == end.y) {
return distance[p.x][p.y];
}
// 枚举四个方向
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
// 如果新的点合法且没有访问过，加入队列
if (isValid(nx, ny) && !visited[nx][ny]) {
q.push({nx, ny});
visited[nx][ny] = true;
distance[nx][ny] = distance[p.x][p.y] + 1;
}
}
}
// 如果没有找到终点，返回-1
return -1;
}

int main() {
Point start = {0, 0};
Point end = {N-1, N-1};
int shortestPath = bfs(start, end);
cout << "Shortest path: " << shortestPath << endl;
return 0;
}