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

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

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

中等 搜索