5251: 迷宫（四）
[Creator : ]
Description
前面的迷宫都是静态的，今天小 A 打算测试一下动态迷宫。迷宫中有一些动态楼梯，它们每隔一分钟就变动一次方向。
比如下面的例子里，一开始楼梯在竖直方向，一分钟以后它移动到了水平方向，再过一分钟它又回到了竖直方向。小 A 发现对他来说很难找到能使得他最快到达目的地的路线，这时聪明的小 A 便想到了万能的你，来解决这个问题。
比如下面的例子里，一开始楼梯在竖直方向，一分钟以后它移动到了水平方向，再过一分钟它又回到了竖直方向。小 A 发现对他来说很难找到能使得他最快到达目的地的路线，这时聪明的小 A 便想到了万能的你，来解决这个问题。
Input
第一行有两个数 MMM 和 NNN。
接下来是一个 MMM 行 NNN 列的地图，'*'表示障碍物，'.'表示走廊，'|'或者'-'表示一个楼梯，并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向，'-'表示的楼梯在一开始是水平方向。地图中还有一个'S'是小 A 的位置，'T'是目标，0≤M,N≤200 \le M,N \le 200≤M,N≤20，地图中不会出现两个相连的梯子。小 A 每秒只能停留在'.'或'S'和'T'所标记的格子内。
接下来是一个 MMM 行 NNN 列的地图，'*'表示障碍物，'.'表示走廊，'|'或者'-'表示一个楼梯，并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向，'-'表示的楼梯在一开始是水平方向。地图中还有一个'S'是小 A 的位置，'T'是目标，0≤M,N≤200 \le M,N \le 200≤M,N≤20，地图中不会出现两个相连的梯子。小 A 每秒只能停留在'.'或'S'和'T'所标记的格子内。
Output
输出一个整数，表示到达目标的最短时间。
注意：小 A 只能每次走到相邻的格子而不能斜走，每移动一次恰好为一分钟，并且小 A 登上楼梯并经过楼梯到达对面的整个过程只需要一分钟，小 A 从来不在楼梯上停留。并且每次楼梯都恰好在小 A 移动完毕以后才改变方向。
注意：小 A 只能每次走到相邻的格子而不能斜走，每移动一次恰好为一分钟，并且小 A 登上楼梯并经过楼梯到达对面的整个过程只需要一分钟，小 A 从来不在楼梯上停留。并且每次楼梯都恰好在小 A 移动完毕以后才改变方向。
Constraints
$1 ≤ N, M ≤ 10$
Sample 1 Input
5 5
**..T
**.*.
..|..
.*.*.
S....
Sample 1 Output
7
Sample 2 Input
5 5
**..T
**.*.
.*|..
.*.*.
S...*
Sample 2 Output
8