题面

小明来到一个由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。

思路

0/1bfs的变种，边权由0/1变为了3/1
很显然可以采用优先队列求解，复杂度O(n×m×log(n×m))
对于0/1bfs，我们通过利用双端队列的特性，将边权0的点插入队首，将边权1的点插入队来高效求解，
那么对于本题，我们可以采用滚动队列的思路进行优化
开四个队列q[4]
假设当前在处理q[0]，那么遇到边权为1的点，就放进q[1]。如果边权为3，就放进q[4]
也就是在处理q[cur]时，将边权为1的点放进q[(cur+1)%4]，将边权为3的点放进q[(cur+3)%4]
在处理完q[cur]后，继续处理q[(cur+1)%4]，直到全部队列为空即可
这样就可以做到按边权大小先后处理，同时复杂度O(n×m)
思路来源于学长,有感而发写 水 一发题解

//注意一个坑点，传送门到到达的点不一定比走过去快，所以传送门传送过去的点不要标记vis
#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int n,m,port;
struct info{
    int x,y;
}st,ed;
bool in(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}
void solve(){
  vector<vector<char>> mp(n+1,vector<char>(m+1));
  vector<vector<int>> dist(n+1,vector<int>(m+1));
  vector<vector<bool>> vis(n+1,vector<bool>(m+1,0));
  unordered_map<int,int> porter;
  queue<pair<int,int>> q[4];
  for(int i = 1;i<=n;i++){
    for(int j = 1;j<=m;j++){
      cin>>mp[i][j];
      dist[i][j]=-1;
      if(mp[i][j]=='S'){
          st.x=i;st.y=j;
      }
      if(mp[i][j]=='T'){
          ed.x=i;ed.y=j;
      }
    }
  }
  while(port--){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    x1++;y1++;x2++;y2++;//注意给出的坐标从0开始
    if(mp[x1][y1]=='#'||mp[x2][y2]=='#')continue;
    porter[x1*1000+y1]=x2*1000+y2;
  }
  int cur = 0;
  dist[st.x][st.y]=0;
  vis[st.x][st.y]=1;
  int val = st.x*1000+st.y;
  if(porter[val]!=0){
    int _x = porter[val]/1000,_y = porter[val]%1000;
    dist[_x][_y]=dist[st.x][st.y]+3;
    if(_x==ed.x&&_y==ed.y){
      cout<<dist[_x][_y]<<'\n';return ;
    }
    q[(cur+3)%4].push(make_pair(_x,_y));
  }
  q[0].push(make_pair(st.x,st.y));
  while(!q[0].empty()||!q[1].empty()||!q[2].empty()||!q[3].empty()){//还有点没处理完
    while(!q[cur].empty()){
      pair<int,int> now = q[cur].front();q[cur].pop();
      int x = now.first,y = now.second;
      for(int i = 0;i<4;i++){
        int nx = x+dir[i][0],ny = y+dir[i][1];
        if(in(nx,ny)&&mp[nx][ny]!='#'&&!vis[nx][ny]){
          dist[nx][ny]=dist[x][y]+1;
          vis[nx][ny]=1;
          if(nx==ed.x&&ny==ed.y){
              cout<<dist[nx][ny]<<'\n';return ;
          }
          q[(cur+1)%4].push(make_pair(nx,ny));
          int val = nx*1000+ny;
          if(porter[val]!=0){
            int _x = porter[val]/1000,_y = porter[val]%1000;
            dist[_x][_y]=dist[x][y]+4;
            if(_x==ed.x&&_y==ed.y){
              cout<<dist[_x][_y]<<'\n';return ;
            }
            q[(cur+3)%4].push(make_pair(_x,_y));
          }
        }
      }
    }
    cur=(cur+1)%4;//滚动
  }
  cout<<-1<<"\n";
  return ;
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//cout << firstxed << secondtprecision(3);
//cout << right << left << secondtw(3);
//int _; cin >> _; while(_--)
  while(cin>>n>>m>>port)
  solve();
  return 0;
}