A38149. 走迷宫一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。 给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。输入第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（1<= R，C <= 40) 接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。 空地格子用'.'表示，有障碍物的格子用'#'表示。 迷宫左上角和右下角都…
填空题
困难
知识点
题目描述
走迷宫
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。 给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
输入
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（1<= R，C <= 40) 接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。 空地格子用'.'表示，有障碍物的格子用'#'表示。 迷宫左上角和右下角都是'.'。
输出
输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
样例输入
5 5
..###
#....
#.#.#
#.#.#
#.#..
样例输出
9
参考答案
#include<iostream>
using namespace std;
#include<string.h>
typedef pair<int, int> PII;
const int N = 50;
char g[N][N];
int h[N][N];
int n, m;
PII que[N * N];
int bfs() {
int dx[] = {
0,1,0,-1
}
, dy[] = {
1,0,-1,0
}
;
int hh = 0, tt = 0;
memset(h, -1, sizeof h);
h[0][0] = 1;
que[0] = {
0,0
}
;
while (hh <= tt) {
auto t = que[hh++];
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && h[x][y] == -1 && g[x][y] == '.') {
h[x][y] = h[t.first][t.second] + 1;
que[++tt] = {
x,y
}
;
}
}
}
return h[n - 1][m - 1];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
上一题
下一题