0-1 迷宫最短路

题目描述

给定一个 N 行 M 列的网格迷宫，字符含义如下：. 表示普通格子，经过花费 0；* 表示特殊格子，经过花费 1；S 表示起点；T 表示终点。每一步可以向上、下、左、右四个方向移动。经过普通格子花费 0，经过特殊格子花费 1。起点和终点视为普通格子（花费 0）。求从起点到终点的最小花费。如果无法到达，输出 -1。

输入格式

第一行两个整数 N 和 M。接下来 N 行，每行 M 个字符，描述迷宫。保证有且只有一个 S 和一个 T。

输出格式

输出一个整数，表示最小花费。如果无法到达，输出 -1。

样例

样例输入

3 3
S..
.**
..T

样例输出

0

数据范围与提示

$1 \le N, M \le 500$