题意

走迷宫，入口是S，出口是T，和普通的走迷宫不同，这个迷宫存在传送门，即从一个坐标直接传送到另一个，有一个问题，传送终点如果是陷阱就不能使用，走一格耗时1s，传送一次耗时3s，走到传送门面前时可以选择不传送。

输入描述

有多组数据。对于每组数据：
第一行有三个整数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。

解析

裸的bfs问题，需要注意的是否使用传送门，我看了别人的题解，在不使用优先队列的情况下可以在使用传送门之后加入队列但是不进行标记，这样就相当于对那一个点两种方案都试一下，我采用的是使用优先队列，队伍中始终优先步数更少的走法，加入队列的时候不标记，从队列拿出来的时候标记，这样子只要直接走过去比传送门传送过去更快的话就是先处理直接走过去的，等轮到传送门的时候这个地方已经标记了，就不会再进行搜索。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=325;
char mp[N][N];
int vis[N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n,m,q;
map<pair<int,int>,pair<int,int>> map_1;

struct node {
    int x, y, step;
    node(const int &x = 0, const int &y = 0, const int &step = 0) :
        x(x), y(y), step(step) {}               //设定初始值
    bool operator<(const node & obj) const {
        return step > obj.step;             //设定优先队列的比较方式
    }
};

bool check(int x,int y){
    if (x <= 0 || y <= 0 || x > n || y > m) return false;
    return true;
}

int sx,sy;
int bfs(){
    priority_queue<node> q;
    q.emplace(sx,sy,0);
    while(!q.empty()){
        node k=q.top();
        q.pop();
        if(vis[k.x][k.y]) continue;
        if(mp[k.x][k.y]=='T')
            return k.step;
        vis[k.x][k.y]=1;
        for (int i = 0; i < 4; i++) {
            int tx = k.x + dx[i];
            int ty = k.y + dy[i];
            if (check(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty]) {
                q.emplace(tx, ty, k.step + 1);
            }
        }
        if (map_1.count({k.x, k.y})) {
            int tx = map_1[{k.x, k.y}].first;
            int ty = map_1[{k.x, k.y}].second;
            if (check(tx, ty) && mp[tx][ty] != '#' && !vis[tx][ty]) {
                q.emplace(tx, ty, k.step + 3);
            }
        }
    }
    return -1;
}

int main(void){
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>q){
        map_1.clear();
        memset(vis,0,sizeof(vis));  //将路径清除
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){   //吐槽一下这里debug了半天只是因为一开始的时候手快写错了
                cin>>mp[i][j];
                if(mp[i][j]=='S')
                    sx=i,sy=j;
            }
        }
        for(int i=0;i<q;++i){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            map_1[{++a,++b}]={++c,++d};
        }
        cout<<bfs()<<endl;
    }
    return 0;
}