Problem1100--诡异的楼梯

1100: 诡异的楼梯

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 681  Solved: 122
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI准备去升华楼的404自习室上晚自习,但是他发现某些楼梯并不是静止不动的,相反,他们每隔一分钟就变动一次方向.
PIPI发现对他来说很难找到能使得他最快自习室的路线,胖虎能够帮帮PIPI吗?
注: PIPI只能每次走到相邻的格子而不能斜走,每移动一次恰好为一分钟,并且PIPI登上楼梯并经过楼梯到达对面的整个过程只需要一分钟,PIPI从来不在楼梯上停留。并且每次楼梯都恰好在PIPI移动完毕以后才改变方向.
http://acm.hdu.edu.cn/data/images/C6-1003.gif

Input

测试数据有多组。
对于每组测试用例:
第一行有两个数,M和N。
接下来是一个M行N列的地图,'*'表示障碍物,'.'表示走廊,'|'或者'-'表示一个楼梯。'|'表示的楼梯在最开始是竖直方向,'-'表示的楼梯在一开始是水平方向.
地图中还有一个'S'是PIPI的起点,'T'是自习室的位置,0<=M,N<=20,地图中不会出现两个相连的梯子.PIPI每秒只能停留在'.'或'S'和'T'所标记的格子内.

Output

对于每组测试用例,输出仅一行,包含一个数T,表示到达目标的最短时间.如果到达不了目标,输出-1.

Sample Input

5 5
**..T
**.*.
..|..
.*.*.
S....

Sample Output

7

Source/Category