蒜头君回家(bfs)

题干:蒜头君要回家，但是他家的钥匙在他的朋友花椰妹手里，他要先从花椰妹手里取得钥匙才能回到家。花椰妹告诉他：“你家的钥匙被我复制了很多个，分别放在不同的地方。”

蒜头君希望能尽快回到家中，他首先需要取得任意一把钥匙，请你帮他计算出回家所需要的最短路程。

蒜头君生活的城市可以看做是一个n×m 的网格，其中有道路有障碍，钥匙和家所在的地方可以看做是道路，可以通过。蒜头君可以在城市中沿着上下左右 4 个方向移动，移动一个格子算做走一步。

输入格式
第一行有两个整数 n，m。城市的地图是 n 行 m 列。(1≤n,m≤2000)

接下来的 n 行，每行 m 个字符，代表城市的地图。'.'代表道路，'#'代表障碍物，'S'代表蒜头君所在的位置，'T'代表蒜头家的位置，'P'代表钥匙的位置。除了障碍物以外，别的地方都可以通过。题目保证蒜头君至少有一条路径可以顺利拿到钥匙并且回家。

输出格式
输出蒜头回家要走的最少步数，占一行。

样例输入

8 10
P.####.#P#
..#..#...#
..#T##.#.#
..........
..##.#####
..........
#####...##
###....S##
样例输出

21

#include 
#include 
#include 
using namespace std;
int n, m;
class point
{
public:
    point(int sx, int sy, int snum, int sflag)
    {
        this->x = sx;
        this->y = sy;
        this->num = snum;
        this->flag = sflag;
    }
    int x, y;
    int num, flag;
};//存储结构,包含点坐标,到该点所走的步数以及该点的层级->(找到钥匙前为第0层,找到钥匙变为第1层)
int head[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//四方向搜索
char map1[2001][2001];//存储地图
int visit[2001][2001][2] = {0};//visit多一个维度用来表示层数(每个点每层都可经过一次)
void bfs(int &x, int &y)
{
    queue q;//队列
    q.push(point(x, y, 0, 0));
    visit[x][y][0] = 1;
    while (!q.empty())//非空循环
    {
        point t = q.front();
        q.pop();
        if (map1[t.x][t.y] == 'T' && t.flag == 1)//在第1层找到终点,退出(进入第一层也就是,保证拿到了钥匙)
        {
            cout << t.num;
            return;
        }
        if (map1[t.x][t.y] == 'P')//拿到钥匙,标记改为第1层
            t.flag = 1;

        for (int i = 0; i < 4; i++)
        {
            int jx = t.x + head[i][0];
            int jy = t.y + head[i][1];//遍历四周同深度点
            if (jx < 0 || jx >= n || jy < 0 || jy >= m)//越界就重开
                continue;
            if (!visit[jx][jy][t.flag] && map1[jx][jy] != '#')//该层没来过且不是障碍,就在这层标记该点,并入队
            {
                visit[jx][jy][t.flag] = 1;
                q.push(point(jx, jy, t.num + 1, t.flag));//深度(步数)加1
            }
        }
    }
}
int main()
{

    cin >> n >> m;
    int tx, ty;
    for (int i = 0; i < n; i++) //思路:先第一层找到钥匙 ,再从钥匙处第二层找家(bfs最先找到的就是最近的)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map1[i][j];
            if (map1[i][j] == 'S')//找到入口做好记录
            {
                tx = i;
                ty = j;
            }
        }
    }
    bfs(tx, ty);
    return 0;
}