简答题
偏难
#7315
走出迷宫 当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。 假设你已经得到了一个n*m的迷宫的图纸,…
走出迷宫
当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。
时间限制:1000
内存限制:65536
输入
第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。 接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。
输出
输出从起点到出口最少需要走的步数。
样例输入
3 3 S#T .#. ...
样例输出
6
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int n, m, p[10008], q[10008], ans[108][108], qx, qy, zx, zy;
char a[108][108];
int xx[5] = {0, 1, -1, 0, 0};
int yy[5] = {0, 0, 0, 1, -1};
void bfs() {
a[qx][qy] = '#';
ans[qx][qy] = 0;
int head = 1;
int tail = 1;
p[1] = qx;
q[1] = qy;
while (head <= tail) {
for (int i = 1; i <= 4; i++) {
int h = p[head] + xx[i];
int l = q[head] + yy[i];
if (a[h][l] != '#' && h >= 1 && l >= 1 && h <= n && l <= m) {
a[h][l] = '#';
tail++;
p[tail] = h;
q[tail] = l;
ans[h][l] = ans[p[head]][q[head]] + 1;
if (h == zx && l == zy) {
cout << ans[h][l] << endl;
return;
}
}
}
head++;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == 'S') {
qx = i;
qy = j;
}
if (a[i][j] == 'T') {
zx = i;
zy = j;
}
}
}
bfs();
return 0;
}</pre>
这道题暂未补解析。