题目描述
一张 行 列的地图：. 空地、# 墙，恰好一个 S 和一个 T（均为空地）。测绘员承认：地图上恰好有一个墙格其实标错了——它实际是空地（但不知道是哪一个）。现在想知道：在最有利的情况下（即选那个标错的墙来修正）， 到 的最少步数最小可能是多少？四邻移动，每步 1 分钟。若无论修正哪个墙都连不通，输出 -1。
输入格式
第一行两个整数 ；接下来 行每行一个长度为 的字符串（保证至少有一个 #）。
输出格式
一行一个整数，修正后 到 的最小可能步数或 -1。
样例
输入
3 5 S#... .#.#. ...#T
输出
6
数据范围
- 30% ,50 且 # 不超过 200 个（逐个修正后重新 BFS 也能过）。
- 60% ,500 且 # 不超过 2000 个。
- 100% ,1000，# 不超过 的一半。