C-最短补货路径（supply）

题目背景

在一座大型仓库中，机器人需要从起点出发，把货物送到终点。

但是这次任务有一个额外要求： 机器人在到达终点前， 必须至少经过一个补给点 ，以便补充电量。

仓库被看作一个二维网格图，其中有些位置可以通行，有些位置是障碍物。你的任务是求出机器人满足要求时的最短路径长度。

题目描述

给定一个 $n \times m$ 的字符网格，其中每个位置可能是以下五种字符之一：

• S：起点，恰有一个；
• T：终点，恰有一个；
• P：补给点，可以有多个；
• .：空地，可以通行；
• #：障碍，不能通行。

机器人每次可以向上、下、左、右四个方向移动一格，前提是目标位置不是障碍物。

请你求出从 S 出发，到达 T，并且 路径中至少经过一个 P 的最短路径长度。

如果不存在满足条件的路径，输出 -1。

输入格式

第一行输入两个整数 $n,m$，表示网格的行数和列数。

接下来输入 $n$ 行字符串，每行长度为 $m$，描述整个网格。

输出格式

输出一个整数，表示满足要求的最短路径长度。

如果不存在这样的路径，输出 -1。

输入输出样例

输入 #1

4 5
S..#P
.#...
P..#.
..T..

输出 #1

5

样例解释

一种最优走法是：

• 从 S 先走到左下角的补给点 P；
• 再从这个补给点走到 T。

对应路径长度为：

• S 到 P：$2$ 步；
• P 到 T：$3$ 步。

总长度为：

数据范围

对于所有测试数据，保证：$1 \le n,m \le 1000,\quad 1 \le n \times m \le 2 \times 10^5$

并保证：

• 网格中恰有一个 S；
• 网格中恰有一个 T；
• 字符只会是 S、T、P、.、# 之一。

本题共设 $20$ 个测试点，各测试点满足的限制如下：

特殊性质 $A$：保证网格中恰有一个补给点 P。

特殊性质 $B$：保证网格中没有障碍物 #。

特殊性质 $D$：保证所有补给点 P 都可以从 S 到达，且都可以到达 T。

特殊性质 $E$：保证网格恰有一行，即 $n=1$。

特殊性质 $F$：保证网格恰有一列，即 $m=1$。

特殊性质 $G$：保证补给点 P 的数量不超过 $2$。