迷宫最短路

题目描述

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感。 如果你能拿到迷宫的地图，事情就会简单很多。

现在，假设你已经得到了一个大小为 (n \times m) 的迷宫图纸，请你找出 从起点到出口的最短路径长度。

迷宫中：

• '.' 表示空地，可以通行；
• '#' 表示墙，不可通行；
• 'S' 表示起点；
• 'T' 表示出口。

你可以从起点开始，每一步移动到 上下左右 四个相邻格中的一个（前提是该格不越界且不是墙），求从 S 走到 T 至少需要多少步。

输入格式

第一行包含两个整数

n m

表示迷宫的行数和列数。 接下来 (n) 行，每行一个长度为 (m) 的字符串，表示整个迷宫的布局。

• 字符 '.' 表示空地；
• 字符 '#' 表示墙；
• 字符 'S' 表示起点；
• 字符 'T' 表示出口。

数据范围：

• $(1 \le n, m \le 100)$

（保证迷宫中恰有一个 S 和一个 T。）

输出格式

输出一个整数，表示从起点到出口最少需要走的步数。

样例输入

3 3
S#T
.#.
...

样例输出

6