You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

机器人巡馆

题目描述

校园科技馆是一个 $n$ 行 $m$ 列的网格。. 表示空地，# 表示障碍物，S 表示起点，T 表示终点。

机器人每一步可以向上、下、左、右移动一格，不能走出网格。机器人携带了一次性破障装置：在整个移动过程中，它最多可以清除一个障碍物格子 #，并进入该格子。

请你求出机器人从 S 到达 T 所需的最少步数；若无法到达，输出 -1。

输入格式

第一行两个整数 $n,m$。接下来 $n$ 行，每行一个长度为 $m$ 的字符串。保证恰好有一个 S 和一个 T。

输出格式

输出最少步数，无法到达则输出 -1。

样例输入

4 6
S..#..
...#..
...#..
...#.T

样例输出

8

样例解释

第 $4$ 列形成障碍墙。机器人必须清除其中一个障碍物才能进入右侧区域，最少走 $8$ 步。

数据范围

• $1 \le n,m \le 1000$；
• $n\times m \le 10^6$。