8372: 水火迷宫
[Creator : ]
Description
精通程序设计的 Applese 双写了一个游戏。
在这个游戏中，它被困在了一个 $n\times m$ 的迷宫中，它想要逃出这个迷宫。
在迷宫中，有一些方格是水池，只有当 Applese 处于水属性的时候才可以通过；有一些方格是岩浆，只有当 Applese 是火属性的时候可以通过；有一些方格是墙壁，无论如何都无法通过；另一些格子是空地（包括起点和终点），可以自由通过。
在一些空地上有神秘道具可以让 Applese 转换自己的属性（从水属性变为火属性或从火属性变为水属性，需要一个单位的时间）。
已知 Applese 在一个单位的时间内可以朝四个方向行走一格，且开始处于水属性，位于空地的道具拾取后只能在该处立即使用（或者不使用），且可以多次使用。
求它走出迷宫需要的最少时间。
在这个游戏中，它被困在了一个 $n\times m$ 的迷宫中，它想要逃出这个迷宫。
在迷宫中，有一些方格是水池，只有当 Applese 处于水属性的时候才可以通过；有一些方格是岩浆，只有当 Applese 是火属性的时候可以通过；有一些方格是墙壁，无论如何都无法通过；另一些格子是空地（包括起点和终点），可以自由通过。
在一些空地上有神秘道具可以让 Applese 转换自己的属性（从水属性变为火属性或从火属性变为水属性，需要一个单位的时间）。
已知 Applese 在一个单位的时间内可以朝四个方向行走一格，且开始处于水属性，位于空地的道具拾取后只能在该处立即使用（或者不使用），且可以多次使用。
求它走出迷宫需要的最少时间。
Input
第一行两个正整数 $n, m\ (1 \leq n,m\leq 1,000)$，表示迷宫的大小。
接下来 n 行，每行长度为 m 的字符串。描述地图。
其中 ‘S’ 表示起点，‘T’ 表示终点，’.’ 表示空地，‘w’ 表示岩浆，’~‘ 表示水池，’@’ 表示道具，’#' 表示障碍。
保证地图中的起点和终点只有一个，道具都位于空地。
接下来 n 行，每行长度为 m 的字符串。描述地图。
其中 ‘S’ 表示起点，‘T’ 表示终点，’.’ 表示空地，‘w’ 表示岩浆，’~‘ 表示水池，’@’ 表示道具，’#' 表示障碍。
保证地图中的起点和终点只有一个，道具都位于空地。
Output
一行一个整数表示答案。如果无法走出迷宫，输出 -1。
Sample 1 Input
5 5
.w@..
.S#..
~w#..
.w..~
@w.~T
Sample 1 Output
18