该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

贪玩啊 / maze

时间限制：1.00s
内存限制：128.00MB
提交文件：maze.cpp
输入文件：maze.in
输出文件：maze.out

题目描述

贪玩的你不小心掉进了一个迷宫，迷宫可以视作一个 $n*m$ 的网格。

你每次可以走到与所在位置四联通相邻的没有障碍的空地上（也就是上下左右）。

给出你初始所在的位置，出口位置以及障碍，请问在最好的情况下，最少走多少步你能走出迷宫？

输入格式

第一行两个整数 $n,m$，表示迷宫的大小。

接下来 $n$ 行每行 $m$ 个字符，‘#’表示障碍，‘.’表示没有障碍，‘S’表示你的初始位置，‘T’表示出口。

输出格式

输出一行一个整数，如果能走出迷宫，请输出最好情况下最少需要多少步能走出迷宫，否则输出 $-1$。

4 4
.#S#
T#.#
.#..
...#

7

5 4
#..#
.#.S
.#..
T#.#
#.#.

-1

数据范围

#1 - #4: $1≤n,m ≤10$;

#5 - #10: $1≤n,m ≤1000$。