魔法之森的蘑菇
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红在魔法之森迷路了,森林中有一些致幻的毒蘑菇。森林用一个 n 行 m 列的矩阵表示。
小红为了方便辨别方向,她在遇到蘑菇之前都不会进行转弯。当小红遇到蘑菇时,她可以选择向一个方向转弯或者继续直走(但不能掉头)。
现在小红想知道,自己从 S 点走到 T 点的最短步数是多少?
ps:请注意,小红初始的前进方向可以任意选择。

输入描述:

本题有多组测试数据。
第一行一个正整数T\ (1 \leq T \leq 100),表示测试数据组数。
接下来,对于每组测试数据:
第一行输入两个正整数n,m,代表矩阵的行数和列数。
接下来的n行,每行输入一个长度为m的字符串,用来表示森林地图。
保证恰好有一个'S'字符和一个'T'字符,其余字符均为'.'和'*'和'#',其中'.'代表道路,'*'代表蘑菇,'#'代表障碍物,无法通过。
1\leq n,m \leq 1000
(保证所有测试数据中,n 的总和和 m 的总和不超过 1000

输出描述:

输出包括T 行,每行一个数字表示每组测试数据的答案。
如果小红无法到达目的地,则输出-1。
否则输出一个正整数,代表小红的行走步数。
示例1

输入

复制
1
3 3
S..
.T*
*.*

输出

复制
6

说明

下,下,(左转)右,右,(左转)上,(左转)左。
示例2

输入

复制
1
1 5
S.*.T

输出

复制
4

说明

遇到蘑菇也可以不改变方向。
示例3

输入

复制
1
2 2
S#
#T

输出

复制
-1

说明

小红无法行走,障碍物阻碍了所有的路线。