定义一个二维数组maze[5][5],它表示一个5*5的迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
时间: 2024-06-12 07:04:04 浏览: 194
这道题可以使用广度优先搜索算法(BFS)来解决。
首先定义一个队列,将起点(即maze[0][0])加入队列中。然后进入循环,每次从队列中取出一个元素(表示当前所在的位置),如果这个位置是终点(即maze[4][4]),则找到了最短路线,返回路径长度即可;否则,将当前位置的所有可行的相邻位置加入队列中,并将它们标记为已访问,同时记录它们到起点的距离(即在当前位置的基础上加1)。重复这个过程,直到队列为空或找到终点为止。
下面是具体的代码实现:
```
#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},
{1, 0, 1, 1, 0},
{0, 0, 0, 1, 0}
};
struct Point {
int x, y, step;
};
int bfs() {
queue<Point> q;
Point start = {0, 0, 0};
q.push(start);
maze[0][0] = 1; // 标记起点已访问
while (!q.empty()) {
Point p = q.front();
q.pop();
if (p.x == N-1 && p.y == N-1) { // 找到终点
return p.step;
}
// 将可行的相邻位置加入队列
if (p.x > 0 && maze[p.x-1][p.y] == 0) {
q.push({p.x-1, p.y, p.step+1});
maze[p.x-1][p.y] = 1; // 标记已访问
}
if (p.x < N-1 && maze[p.x+1][p.y] == 0) {
q.push({p.x+1, p.y, p.step+1});
maze[p.x+1][p.y] = 1; // 标记已访问
}
if (p.y > 0 && maze[p.x][p.y-1] == 0) {
q.push({p.x, p.y-1, p.step+1});
maze[p.x][p.y-1] = 1; // 标记已访问
}
if (p.y < N-1 && maze[p.x][p.y+1] == 0) {
q.push({p.x, p.y+1, p.step+1});
maze[p.x][p.y+1] = 1; // 标记已访问
}
}
return -1; // 没有找到终点
}
int main() {
cout << bfs() << endl;
return 0;
}
```
输出结果为3,表示从左上角到右下角的最短路线长度为3。
阅读全文