问题描述

蒜头君要回家，但是他家的钥匙在他的朋友花椰妹手里，他要先从花椰妹手里取得钥匙才能回到家。花椰妹告诉他：“你家的钥匙被我复制了很多个，分别放在不同的地方。” 蒜头君希望能尽快回到家中，他需要首先取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。 蒜头君生活的城市可以看做是一个n×m 的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过。蒜头君可以在城市中沿着上下左右 4 个方向移动，移动一个格子算做走一步。 输入格式 第一行有两个整数 n，m。城市的地图是 n 行 m 列。(1≤n,m≤2000) 接下来的 n 行，每行 m 个字符，代表城市的地图。’.’ 代表道路，’#’ 代表障碍物，’S’ 代表蒜头君所在的位置，’T’ 代表蒜头家的位置，’P’代表钥匙的位置。除了障碍物以外，别的地方都可以通过。(题目保证蒜头君至少有一条路径可以顺利拿到钥匙并且回家) 输出格式 输出蒜头回家要走的最少步数，占一行。 样例输入（CSDN编辑器的原因，输入会变形，所以把输入写到代码片里）

8 10

P.####.#P#

..#..#...#

..#T##.#.#

..........

..##.#####

..........

#####...##

###....S##

样例输出 21

AC代码

#include

#include

#include

#include

using namespace std;

queue qx;