0-1 迷宫最短路

给定一个 N x M 的网格迷宫，其中包含以下类型的单元格：

• '.' 表示普通单元格，进入该单元格代价为 0。
• '*' 表示特殊单元格，进入该单元格代价为 1。
• 'S' 表示起点，代价为 0。
• 'T' 表示终点，代价为 0。

你可以向上、下、左、右四个方向移动。请计算从起点 'S' 到终点 'T' 的最小总代价。如果无法到达终点，请输出 -1。

输入格式

第一行包含两个整数 N 和 M，表示网格的行数和列数。 接下来 N 行，每行包含一个长度为 M 的字符串，表示网格的一行。

输出格式

输出一个整数，表示从 'S' 到 'T' 的最小代价。如果无法到达，输出 -1。

样例

3 3
S.*
.**
**T

2

1 3
S*T

1

限制

• 1 ≤ N, M ≤ 500
• 网格中恰好有一个 'S' 和一个 'T'
• 'S' 和 'T' 不在同一位置
• 时间限制：1.0 秒
• 空间限制：256 MB