本文主要是介绍献给阿尔吉侬的花束(信息学奥赛一本通-T1256),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【题目描述】
阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。
迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置,字符E表示奶酪所在的位置,字符#表示墙壁,字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。
【输入】
第一行是一个正整数T(1 ≤ T ≤ 10),表示一共有T组数据。
每一组数据的第一行包含了两个用空格分开的正整数R和C(2 ≤ R, C ≤ 200),表示地图是一个R×C的矩阵。
接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。
【输出】
对于每一组数据,输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。
【输入样例】
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.【输出样例】
5
1
oop!
【源程序】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 300
#define MOD 2520
#define E 1e-12
using namespace std;
int r,c;
char a[N][N];
bool vis[N][N];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node
{int x;int y;int step;
}q[N*100];
void bfs(int sx,int sy,int ex,int ey)
{int head=1,tail=1;bool flag=true;memset(vis,0,sizeof(vis));vis[sx][sy]=1;q[tail].x=sx;q[tail].y=sy;q[tail].step=0;tail++;while(head<tail){int x=q[head].x;int y=q[head].y;int step=q[head].step;if(x==ex&&y==ey){flag=false;printf("%d\n",step);break;}for(int i=0;i<4;i++){int nx=x+dir[i][0];int ny=y+dir[i][1];if(nx>=0&&nx<r&&ny>=0&&ny<c&&vis[nx][ny]==0&&a[nx][ny]=='.'){vis[nx][ny]=1;q[tail].x=nx;q[tail].y=ny;q[tail].step=step+1;tail++;}}head++;}if(flag)printf("oop!\n");
}
int main()
{int t;scanf("%d",&t);while(t--){int start_x,start_y,end_x,end_y;scanf("%d%d",&r,&c);for(int i=0;i<r;i++)scanf("%s",a[i]);for(int i=0;i<r;i++)for(int j=0;j<c;j++){if(a[i][j]=='S'){start_x=i;start_y=j;}if(a[i][j]=='E'){end_x=i;end_y=j;a[i][j]='.';}}bfs(start_x,start_y,end_x,end_y);}return 0;
}
这篇关于献给阿尔吉侬的花束(信息学奥赛一本通-T1256)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!