#250. 走迷宫 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

给出一个 n 行 m 列( 1<= n,m <= 40)的二维迷宫,'S'表示起点,'T' 表示终点,'#' 表示墙壁,'.' 表示平地。

你需要从 'S' 出发走到 'T',每次只能上下左右走动,并且不能走出地图的范围以及不能走到墙壁上。

请你计算出走到终点需要走的最少步数。

输入格式

第一行输入n, m表示迷宫大小。

接下来输入n行字符串表示迷宫,每个字符串长度为m。(地图保证有且仅有一个终点,一个起始点)

输出格式

输出走到终点的最少步数,如果不能走到终点输出−1,占一行。

样例

样例输入

2 3
S.#
..T

样例输出

3