问题 27158. -- 尿神走迷宫

27158: 尿神走迷宫

时间限制: 1 Sec  内存限制: 128 MB
献花: 9  解决: 5
[献花][花圈]

题目描述

    gbn上次误入一个迷宫,迷宫中有一些触发式开关,每次经过这些开关时,会把除开关之外的路变成墙,把墙变成路。'*'表示开关,'#'表示墙,'.'表示路  'S'和'T'表示起点和终点(起点和终点并不是特殊点,会随着开关的触发而改变状态)。

比如一个图

3 3

S*.

*..

#.T

走到一个*上后,图变为

#*#

*##

.##

那么gbn到底能不能走出迷宫,如果可以 请输出最短的步数(因为gbn急着出去学(pao)习(mei)) 如果不能输出-1

输入

输入一个T表示T组数据
然后输入一个n,m表示迷宫大小
接下来输入一个n*m的矩阵描述迷宫
其中‘#'表示墙,'.'表示路,'*'表示开关,'S'表示起点,'T'表示终点。

输出

对于每组数据输出一行 表示结果。

样例输入

1
3 3
S*.
*..
#.T

样例输出

6

提示

来源

[献花][花圈]