TRDD got lost again
题号：NC21821
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

X城市是一个交通十分不便利的城市，城市可以看成一个n * m大小的矩阵， 现在TRDD手里有该城市的地图:一个2*n+1行, 2 *m+1列大小的地图。现在TRDD所在的格子用S表示,机场所在的格子用T表示。 其他格子用空格表示，地图上左右相邻的两个格子如果不能通行用"|"表示， 上下相邻的两个点如果不能通行用"-"表示，”+“表示格子的四个角。 题目保证城市X最外圈无法通行（具体请看样例输入）。
为了能尽快赶到机场，TRDD想请你帮忙计算出他到达机场最少需要走过多少个格子（包括起点S和终点T）。
如果无法到达机场T，则输出"TRDD Got lost...TAT"(不包括双引号)。


输入描述:

第一行读入两个数n, m（1 <= n, m <= 3000)表示X城市的大小。

之后有2 * n + 1行， 每行有2 * m + 1个字符， 用来表示TRDD手里的地图

题目保证S和T都有且仅有一个。

输出描述:

如果TRDD能到达机场， 则输出TRDD最少需要经过几个格子
否则输出"TRDD Got lost...TAT"(不包括双引号)
示例1

输入

复制 
4 3
+-+-+-+
|S| | |
+ +-+-+
| | | |
+ +-+-+
| |T  |
+ +-+ +
|     |
+-+-+-+

输出

复制 
8

说明

TRDD所在的位置为(1, 1)， 机场的位置为(3, 2)
路线为(1, 1) -> (2, 1) -> (3, 1) -> (4, 1) -> (4,2) -> (4,3) -> (3,3) ->(3,2)
共8个格子
示例2

输入

复制 
3 3
+-+-+-+
|S|   |
+ + +-+
| | |T|
+ + +-+
|   | |
+-+-+-+

输出

复制 
TRDD Got lost...TAT

说明

无法从S到达T

备注:

由于数据量过大，建议不要使用scanf("％c")读入，否则可能会TLE。

如果输入样例显示格式有误， 请参考图片：