定义一个二维数组: 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表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
时间: 2023-03-31 10:02:39 浏览: 200
可以回答这个问题。可以使用广度优先搜索算法来找出从左上角到右下角的最短路线。具体实现方法可以参考以下步骤:
1. 定义一个队列,将起点(,)加入队列中。
2. 定义一个二维数组visited,用于记录每个位置是否已经被访问过。
3. 定义一个二维数组directions,用于表示可以走的方向,包括向上、向下、向左、向右。
4. 定义一个二维数组distances,用于记录每个位置到起点的距离。
5. 进入循环,直到队列为空:
a. 取出队列中的第一个位置。
b. 如果该位置是终点(4,4),则跳出循环。
c. 遍历该位置的四个方向,如果该方向可以走且未被访问过,则将该位置加入队列中,并更新visited和distances数组。
6. 输出distances[4][4],即为最短路线的长度。
完整代码如下:
#include <iostream>
#include <queue>
using namespace std;
int maze[5][5] = { , 1, , , ,
, 1, , 1, ,
, , , , ,
, 1, 1, 1, ,
, , , 1, };
bool visited[5][5] = { false };
int distances[5][5] = { };
int directions[4][2] = { {-1,}, {1,}, {,-1}, {,1} };
int bfs(int x, int y) {
queue<pair<int, int>> q;
q.push(make_pair(x, y));
visited[x][y] = true;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (cur.first == 4 && cur.second == 4) {
break;
}
for (int i = ; i < 4; i++) {
int nx = cur.first + directions[i][];
int ny = cur.second + directions[i][1];
if (nx >= && nx < 5 && ny >= && ny < 5 && maze[nx][ny] == && !visited[nx][ny]) {
q.push(make_pair(nx, ny));
visited[nx][ny] = true;
distances[nx][ny] = distances[cur.first][cur.second] + 1;
}
}
}
return distances[4][4];
}
int main() {
int shortestPath = bfs(, );
cout << "The shortest path is: " << shortestPath << endl;
return ;
}