简答题
偏难
#7350
走迷宫 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到…
走迷宫
一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
时间限制:1000
内存限制:65536
输入
第一行是两个整数,R和C,代表迷宫的长和宽。(1<= R,C <= 40) 接下来是R行,每行C个字符,代表整个迷宫。 空地格子用'.'表示,有障碍物的格子用'#'表示。 迷宫左上角和右下角都是'.'。
输出
输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。
样例输入
5 5 ..### #.... #.#.# #.#.# #.#..
样例输出
9
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int idata = 1000 + 5;
char maps[idata][idata];
int judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int Count[idata][idata];
int soux, souy;
int exitx, exity;
bool flag;
int m, n;
int main() {
int i, j;
int tail = 1, head = 0;
cin >> m >> n;
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
cin >> maps[i][j];
if (maps[i][j] == '#')
judge[i][j] = 1;
}
}
judge[1][1] = 1;
Count[1][1] = 1;
x[1] = 1, y[1] = 1;
while (head < tail) {
head++;
for (i = 0; i < 4; i++) {
nx = x[head] + change[i][0];
ny = y[head] + change[i][1];
if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && !judge[nx][ny]) {
judge[nx][ny] = 1;
tail++;
x[tail] = nx;
y[tail] = ny;
Count[x[tail]][y[tail]] = Count[x[head]][y[head]] + 1;
if (nx == m && ny == n) {
flag = 1;
break;
}
}
}
if (flag)
break;
}
cout << Count[m][n] << endl;
return 0;
}</pre>
这道题暂未补解析。