1284: 迷宫(必做)

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:113 Solved:61

Description

小明置身于一个迷宫,请你帮小明找出从起点到终点的最短路程。 小明只能向上下左右四个方向移动。

Input

输入包含多组测试数据。输入的第一行是一个整数T,表示有T组测试数据。 每组输入的第一行是两个整数N和M(1<=N,M<=100)。 接下来N行,每行输入M个字符,每个字符表示迷宫中的一个小方格。 字符的含义如下:‘S’:起点,‘E’:终点,‘-’:空地,可以通过,‘#’:障碍,无法通过 输入数据保证有且仅有一个起点和终点。

Output

对于每组输入,输出从起点到终点的最短路程,如果不存在从起点到终点的路,则输出-1。

Sample Input Copy

1
5 5
S-###
-----
##---
E#---
---##

Sample Output Copy

9