C-光玉小镇_牛客小白月赛27

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

经历过与妻儿生离死别的牛牛，选择成为一名电工，过上平淡的日子。牛牛每天的工作是从家里出发，修理完小镇上所有坏掉的电线杆，然后回家和家人团聚。已知小镇是个 $n\times m$ 的区域，每块格子的类型有以下几种：

‘.’：表示该地点为空地。

‘#’：表示该地点正在施工，牛牛无法移动到该地点。

‘S’：表示牛牛的家。

‘T’：表示此处有一个坏掉的电线杆。

牛牛每秒可以往上/下/左/右四个方向移动一格，且牛牛修理一个电线杆所花的时间为 $t$ 秒，请问牛牛从家里出发修理完电线杆并最后回到家的最短时间是多少？

第一行三个正整数 $n$ , $m$ , $t$ ，其中 $n\leq200$ ， $m\leq200$ ， $t\leq10^{9}$ 。

接下来 $n$ 行，每行 $m$ 个字符，表示小镇的情况。保证地图中仅有一个‘S’，且‘T’的数目大于等于1并且小于等于15。

输出牛牛从家里出发修理完电线杆并最后回到家的最短时间，若牛牛无法修理完所有的电线杆，输出-1。

示例1

复制

3 3 1
...
S#T
...

复制