Problem4805--迷宫(二)

4805: 迷宫(二)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

小 A 在你的帮助下终于逃出了迷宫,但是小 A 并没有沉浸于喜悦之中,而是很快的又陷入了思考,从这个迷宫逃出的最少步数是多少呢?

Input

第一行输入两个整数 nnnmmm,表示这是一个 n×mn \times mn×m 的迷宫。
接下来的输入一个 nnnmmm 列的迷宫。其中'S'表示小 A 的位置,'*'表示墙,无法通过,'.'表示路,小 A 可以通过'.'移动,'T'表示迷宫的出口(每次只能移动到四个与他相邻的位置——上,下,左,右)。

Output

输出整数,表示逃出迷宫的最少步数,如果无法逃出迷宫输出 −1-11

Constraints

$1 \le n, m \le 10$。

Sample 1 Input

3 4
S**.
..*.
***T

Sample 1 Output

-1

Source/Category

基础算法 4.100.BFS