#J3043. 英雄找宝剑
英雄找宝剑
题目描述
你是一名英雄,你现在要去寻找你的宝剑,现在有一个R*C的迷宫,你在字符S的位置,宝剑在字符E的位置,字符#表示陷阱,字符.表示可以通过,你在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。问你最短时间如何找到自己的宝剑?输入格式
第一行是一个正整数 TT,表示一共有 TT 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 RR 和 CC,表示地图是一个 R×CR×C 的矩阵。
接下来的 RR 行描述了地图的具体内容,每一行包含了 CC 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
输出格式
对于每一组数据,输出你找到宝剑的最少单位时间。
若你找不到宝剑,则输出“oop!”(只输出引号里面的内容,不输出引号)。
每组数据的输出结果占一行。
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.5
1
oop!
提示
数据范围
1<T≤10,
2≤R,C≤200