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

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

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

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

一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。
输入描述:
有多组数据。对于每组数据：
第一行有三个整数n,m,q(2≤ n,m≤300,0≤ q ≤ 1000)。
接下来是一个n行m列的矩阵，表示迷宫。
最后q行，每行四个整数x1,y1,x2,y2(0≤ x1,x2< n,0≤ y1,y2< m)，表示一个传送阵的入口在x1行y1列，出口在x2行y2列。
输出描述:
如果小明能够活着到达目的地，则输出最短时间，否则输出-1。

思路：这道题需要用到优先队列，不然过不了，详细思路见注释哦，我写得还是比较详细，肯定能懂哒，注意所开数组范围，不然会wa。有错请指教

#include<bits/stdc++.h>
using namespace std;
const int N = 303;
char mp[N][N];//迷宫
int visit[N][N];//判断是否走过，1走过，0未走 
int Qsx[1001];//第i传送门起点x坐标，注意范围，开小了会wa 
int    Qsy[1001];//传送门y起点坐标 
int Qex[1001];//第ig个传送门x终点 
int Qey[1001];
int mark[1001][1001];
int n,m;//迷宫：n行，m列 
int q;//传送门个数 
//左下右上四个方位 
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct Time
{
    int x;
    int y;
    int time;
    friend bool operator<(const Time &a,const Time &b)//定义优先级 
    {
        return a.time >b.time;
    } 

};

int bfs(int sx,int sy)
{
    priority_queue<Time>qu;//结构型优先队列
    if(mp[sx][sy]=='#') return -1;//起点为陷阱 
    qu.push(Time{sx,sy,0});//最初，小明在sx,sy处，所用时间为0 
    while(!qu.empty())
    {
        Time s = qu.top();
        qu.pop();//出队
        if(mp[s.x][s.y]=='T')
        {
            return s.time;//如果到达终点则返回所用时间 
        } 
            Time next;//下一个位置
                     //要么走传送门，走传送门要注意 终点是否为陷阱 
                      //接下来有两种选择，要么上下左右走
         if(mark[s.x][s.y]!=0&&mp[s.x][s.y]!='#')//这个点有传送门而且入口不是陷阱 ，你看我就说用到了吧，
                                                     //嘻嘻 
         {
             int i = mark[s.x][s.y] ;
             if(mp[Qex[i]][Qey[i]]!='#')//传送门终点不是陷阱 ，而且终点没走过 
             {
                 qu.push(Time{Qex[i],Qey[i],s.time+3}); 
            }
         }    
         for(int i=0;i<4;i++)
         {
            //上第二种，下左右走 
                next.x = s.x + dx[i];
                next.y = s.y + dy[i];
                next.time = s.time + 1; 
            //首先判断是否越界 或者是否是陷阱 
               if(next.x<0||next.x>n||next.y<0||next.y>m||mp[next.x ][next.y]=='#') continue;
              //再判断是否走过 
               if(visit[next.x][next.y ]==1) continue;     
               visit[next.x][next.y] = 1;
              // cout<<"普通情况 "<<next.time<<endl; 
               //cout<<next.x<<" "<<next.y<<endl;
               qu.push(next);

         } 

     //    cout<<"a"<<endl; 

    } 
    return -1;//无法走到终点 
}
int main()
{
    while(cin>>n>>m>>q) //多组出入 
    {
            int sx,sy;//起点
               int ex,ey;//终点 
    //输入迷宫 
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]=='S') 
            {
                sx = i;
                sy = j;//记录起点坐标 
            } 

        }
    }
    //输入传送门位置
    int qsx,qsy;//传送门 起点坐标
    int qex,qey;//传送门终点坐标 
    memset(visit,0,sizeof(visit));//利用memset函数，全部标记为0，表示为走过
    memset(mark,0,sizeof(mark));
    for(int i=1;i<=q;i++)//输入传送门 
    {
         cin>>Qsx[i]>>Qsy[i]>>Qex[i]>>Qey[i];
         mark[Qsx[i]][Qsy[i]] = i;//这传送门的起点标记为第i个，在bfs操作了会用到这个 

    } 
    visit[sx][sy] = 1;//起点当然走过啦 
    int ans = bfs(sx,sy);//调用函数，进行bfs操作 
    cout<<ans<<endl;    
    }
    return 0;
}