1101、献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置,字符 E 表示奶酪所在的位置,字符 # 表示墙壁,字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。
解题步骤
代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define x first
#define y second
using namespace std;
const int N = 210;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
int dist[N][N];//判重和距离数组
int bfs(PII start, PII end)
{
queue<PII> q;
memset(dist, -1, sizeof dist);//把距离数组都初始化成-1
dist[start.x][start.y] = 0;//起点开始,距离为0
q.push(start);//起点
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//位置移动x、y数值的变化
while(q.size())
{
PII t = q.front();
//弹出队头
q.pop();
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m)
continue; //出界
if (dist[a][b] != -1)
continue;//走过了
if (g[a][b] == '#')
continue;//障碍物
dist[a][b] = dist[t.x][t.y] + 1;
if (end == make_pair(a, b))
return dist[a][b];//走到终点了,返回距离
q.push({a, b});
}
}
return -1;
}
int main()
{
int T;
cin >> T;
while(T --)
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
scanf("%s", g[i]);
PII start, end;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'S') start = {i, j};
else if (g[i][j] == 'E') end = {i, j};
int distance = bfs(start, end);
if (distance == -1) printf("oop!\n");
else printf("%d\n", distance);
}
return 0;
}