题目描述

给你一个n行m列的二维迷宫。 'S' 表示起点， 'T' 表示终点， '#' 表示墙壁，'.' 表示平地。你需要从 'S' 出发走到 'T' ，每次只能上下左右走动，并且不能走出地图的范围以及不能走到墙壁上。请你计算出走到终点需要走的最少步数。

输入格式

第一行是两个整数n和m(1≤n,m≤100)，表示迷宫的行数和列数。

接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符‘.’表示空地，‘#’表示墙，‘S’表示起点,‘T’表示出口。

输出格式

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

样例

2 3
S.#
..T

3

3 3
..#
S#.
.#T

-1

限度

1s, 1024KiB for each test case.