题目描述】 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。 【输入】 第一行是两个整数,R和C,代表迷宫的长和宽。( 1<= R,C <= 40) 接下来是R行,每行C个字符,代表整个迷宫。 空地格子用‘.’表示,有障碍物的格子用‘#’表示。 迷宫左上角和右下角都是‘.’。 【输出】 输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。 【输入样例】 5 5 ..### #.... #.#.# #.#.# #.#.. 【输出样例】 9(用C++代码实现)
时间: 2024-04-13 09:29:12 浏览: 24
你好!对于这个问题,你可以使用广度优先搜索(BFS)来解决。下面是一个用C++实现的示例代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct Point {
int x, y;
int step;
};
int minSteps(int R, int C, char maze[][40]) {
// 定义四个方向的移动增量
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 定义访问数组,初始值为false
bool visited[40][40] = {false};
// 定义起点和终点
Point start = {0, 0, 0};
Point end = {R-1, C-1, 0};
// 使用BFS进行搜索
queue<Point> q;
q.push(start);
visited[start.x][start.y] = true;
while (!q.empty()) {
Point curr = q.front();
q.pop();
if (curr.x == end.x && curr.y == end.y) {
return curr.step; // 找到终点,返回步数
}
// 向四个方向移动
for (int i = 0; i < 4; i++) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
// 判断移动后的位置是否合法
if (nx >= 0 && nx < R && ny >= 0 && ny < C && !visited[nx][ny] && maze[nx][ny] == '.') {
Point next = {nx, ny, curr.step + 1};
q.push(next);
visited[nx][ny] = true;
}
}
}
return -1; // 如果无法到达终点,返回-1
}
int main() {
int R, C;
cin >> R >> C;
char maze[40][40];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> maze[i][j];
}
}
int steps = minSteps(R, C, maze);
cout << steps << endl;
return 0;
}
```
你可以将输入样例复制到代码中进行测试。希望能帮到你!