链接：https://ac.nowcoder.com/acm/problem/15665 来源：牛客网

小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。

小明只能向上下左右相邻的格子移动，每移动一次花费1秒。

有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。

一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。

做法

调了一个晚上的水题（），如果没有传送阵，那么就是普通的bfs，但如果加了传送阵，我们就应该每次先选择步数小的先走，这样才能保证走到终点的步数最小，传送门可以拿map记录一下位置，注意要先把起始点的传送门放进队列。

或者我们可以不用优先队列，我们记录一下走到某个x y位置的最小步数，最后输出终点的步数就行。

//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
//dont forget to check long long
struct node{
    int x,y,step;
   bool operator < (const node &t)const{
        return step>t.step;
    }
};
struct nd{
    int x,y;
}st,ed;
int n,m,qq;
char s[310][310];
std::map<int,int> mp;
std::priority_queue<node> q;
bool vis[310][310];
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs()
{
    q.push({st.x,st.y,0});
    if(mp[st.x*m+st.y]!=0)
    {
        int pos=mp[st.x*m+st.y];
        int x=pos/m;
        int y=pos%m;
        q.push((node){x,y,3});
    }
    while(!q.empty())
    {
        auto cur=q.top();
        q.pop();
         if(cur.x<0||cur.y<0||cur.x>=n||cur.y>=m||vis[cur.x][cur.y]||s[cur.x][cur.y]=='#') continue;
        vis[cur.x][cur.y]=true;
        //std::cout<<x<<" "<<y<<endl;
        if(cur.x==ed.x&&cur.y==ed.y)
        {
            std::cout<<cur.step<<endl;
            return ;
        }
        vis[cur.x][cur.y]=true;
         
        for(int i=0;i<4;i++)
        {
            int dx=cur.x+d[i][0];
            int dy=cur.y+d[i][1];
            q.push((node){dx,dy,cur.step+1});
        }
        if(mp[cur.x*m+cur.y]!=0)
        {
            int pos=mp[cur.x*m+cur.y];
            int x=pos/m;
            int y=pos%m;
            q.push((node){x,y,cur.step+3});
        }
       
    }
    std::cout<<-1<<endl;
}
void slove()
{
     
     while(std::cin>>n>>m>>qq)
     {
         while(!q.empty()) q.pop();
        mp.clear();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                std::cin>>s[i][j];
                if(s[i][j]=='S') 
                {
                    
                    st={i,j};
                    
                }
                if(s[i][j]=='T')
                {
                    ed={i,j};
                    //std::cout<<ex<<" "<<ey<<endl;
                }
                vis[i][j]=false;
                
            }
        }
        for(int i=1;i<=qq;i++)
        {
            int x1,y1,x2,y2;
            std::cin>>x1>>y1>>x2>>y2;
           mp[x1*m+y1]=(x2*m+y2);
        }
        
      bfs();
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T=1;
    //std::cin>>T;
    while(T--)
    {
        slove();
    }

    return 0;
}