4805: 迷宫(二)
[Creator : ]
Description
小 A 在你的帮助下终于逃出了迷宫,但是小 A 并没有沉浸于喜悦之中,而是很快的又陷入了思考,从这个迷宫逃出的最少步数是多少呢?
Input
第一行输入两个整数 nnn 和 mmm,表示这是一个 n×mn \times mn×m 的迷宫。
接下来的输入一个 nnn 行 mmm 列的迷宫。其中'S'表示小 A 的位置,'*'表示墙,无法通过,'.'表示路,小 A 可以通过'.'移动,'T'表示迷宫的出口(每次只能移动到四个与他相邻的位置——上,下,左,右)。
接下来的输入一个 nnn 行 mmm 列的迷宫。其中'S'表示小 A 的位置,'*'表示墙,无法通过,'.'表示路,小 A 可以通过'.'移动,'T'表示迷宫的出口(每次只能移动到四个与他相邻的位置——上,下,左,右)。
Output
输出整数,表示逃出迷宫的最少步数,如果无法逃出迷宫输出 −1-1−1。
Constraints
$1 \le n, m \le 10$。
Sample 1 Input
3 4
S**.
..*.
***T
Sample 1 Output
-1