9919: 带状态迷宫
[Creator : ]
Description
小明要回家，但是他家的钥匙在他的朋友小王手里，他要先从小王手里取得钥匙才能回到家。小王告诉他：“你家的钥匙被我复制了很多个，分别放在不同的地方。”
小明希望能尽快回到家中，他需要首先取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。
小明生活的城市可以看做是一个 $n \times m$ 的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过。小明可以在城市中沿着上下左右 $4$ 个方向移动，移动一个格子算做走一步。
小明希望能尽快回到家中，他需要首先取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。
小明生活的城市可以看做是一个 $n \times m$ 的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过。小明可以在城市中沿着上下左右 $4$ 个方向移动，移动一个格子算做走一步。
Input
第一行有三个整数 $n,m\ (1 \leq n,m \leq 2,000)$。城市的地图是 $n$ 行 $m$ 列。
接下来的 $n$ 行，每行 $m$ 个字符，代表城市的地图。'.' 代表道路，'#' 代表障碍物，'S' 代表小明所在的位置，'T' 代表小明家的位置，'P' 代表钥匙的位置。除了障碍物以外，别的地方都可以通过。
题目保证小明至少有一条路径可以顺利拿到钥匙并且回家。
接下来的 $n$ 行，每行 $m$ 个字符，代表城市的地图。'.' 代表道路，'#' 代表障碍物，'S' 代表小明所在的位置，'T' 代表小明家的位置，'P' 代表钥匙的位置。除了障碍物以外，别的地方都可以通过。
题目保证小明至少有一条路径可以顺利拿到钥匙并且回家。
Output
输出回家要走的最少步数，占一行。
Sample 1 Input
8 10
P.####.#P#
..#..#...#
..#T##.#.#
..........
..##.#####
..........
#####...##
###....S##
Sample 1 Output
21
Sample 2 Input
10 13
#############
#P#.S.#...#T#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#...#...#...#
#############
Sample 2 Output
77
Sample 3 Input
10 13
#############
#P#.S.#.P.#T#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#.#.#.#.#.#.#
#...#...#...#
#############
Sample 3 Output
39