寻找郑州网站建设,用模板做网站,设计师网站pin,上海网站建设信息网阿尔吉侬是一只聪明又慵懒的小白鼠#xff0c;它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫#xff0c;研究员们为了鼓励阿尔吉侬尽快到达终点#xff0c;就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道#xff0c;如果阿尔吉侬足够聪明…阿尔吉侬是一只聪明又慵懒的小白鼠它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫研究员们为了鼓励阿尔吉侬尽快到达终点就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道如果阿尔吉侬足够聪明它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置字符 E 表示奶酪所在的位置字符 # 表示墙壁字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置但不能走出地图边界。
输入格式 第一行是一个正整数 T表示一共有 T 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R 和 C表示地图是一个 R×C 的矩阵。
接下来的 R 行描述了地图的具体内容每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
输出格式 对于每一组数据输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪则输出“oop!”只输出引号里面的内容不输出引号。
每组数据的输出结果占一行。
数据范围 1T≤10, 2≤R,C≤200 输入样例 3 3 4 .S… ###. …E. 3 4 .S… .E… … 3 4 .S… …E. 输出样例 5 1 oop!
代码如下
#include iostream
#include queue
#include cstring
using namespace std;
typedef pairint,intPII;
#define x first
#define y second
const int N 210;
int n,m;
int dx[] {0,0,1,-1},dy[] {1,-1,0,0};
char g[N][N];
int dis[N][N];
int bfs(PII start,PII end)
{memset(dis,-1,sizeof(dis));queuePII q;dis[start.x][start.y] 0;q.push(start);while(q.size()){PII t q.front();q.pop();for (int i 0;i4;i){int x t.xdx[i],y t.ydy[i];if ( x 0 || xn || y 0 || y m ) continue;if (g[x][y]#) continue;if (dis[x][y]!-1) continue;dis[x][y] dis[t.x][t.y]1;if (end make_pair(x,y)) return dis[x][y];q.push({x,y});}}return -1;
}int main()
{int cnt;cincnt;while(cnt--){PII start,end;cinnm;for (int i 0;in;i)scanf(%s,g[i]);for (int i 0;in;i)for (int j 0;jm;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){coutdistanceendl;}else{coutoop!endl;}}return 0;
}
