maze

题意：
给了一个n * m的矩阵，让从起点走到终点的最小花费是多少。
有一些地点可以进行传送，不过需要花费的时间为3，其他的正常上下左右走花费的时间是1。

思路：
挺简单的题。
就是找到起点的位置，对于当前队列头的点，去走四个方向是不是满足要求。
然后再看当前点是不是有传送门，看传送的地点是不是满足即可。
因为要求花费时间最优，边权不都是1，所以用优先队列去bfs即可
第一次到达终点的花费就是最小花费。
对于标记有一个细节
就是如果新的点是通过上下左右直接走到的，肯定可以标记掉，因为是附近的。
但如果是传送门过去的就不要标记，因为传送门过去的不一定最优。
比如从(x,y) 传送到(x,y+2) 传送门要花费3，如果标记掉了，那么就错了 因为直接走过去只需要花费2

当然了这个还是看个人写法。可以直接把满足的都丢尽队列内，第一次取到这个坐标的时候的标记掉这个位置，后面如果在取到这个左边就continue,这样方便点。

偷个懒，优先队列没用结构体存，直接优先队列套两个pair了

#include<bits/stdc++.h>
using namespace std;
char mp[305][305];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
map<pair<int,int>,vector<pair<int,int>>> k;
bool vis[305][305];
int n,m,q;
bool check(int x,int y){

    if(x<0 || x>=n || y<0 || y>=m || vis[x][y] || mp[x][y]=='#') return 1;
    return 0;
}
void bfs(){

    int ex,ey;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]=='S'){
                ex=i;ey=j;break;
            }
        }
    }
    priority_queue<pair<int,pair<int,int>>> q;
    q.push({0,{ex,ey}});
    vis[ex][ey]=1;
    while(!q.empty()){
        pair<int,pair<int,int>> now=q.top();
        int num=now.first;
        int x=now.second.first,y=now.second.second;
        if(mp[x][y]=='T'){
            cout<<-num<<endl;
            return ;
        }
        q.pop();
        for(int i=0;i<4;i++){
            int fx=x+dx[i],fy=y+dy[i];
            if(check(fx,fy)) continue;
            vis[fx][fy]=1;
            q.push({num-1,{fx,fy}});
        }
        for(auto it:k[{x,y}]){
            int fx=it.first,fy=it.second;
            if(check(fx,fy)) continue;
            q.push({num-3,{fx,fy}});
        }
    }
    cout<<-1<<endl;

}
int main(){
    while(cin>>n>>m>>q){

        for(int i=0;i<n;i++) cin>>mp[i];
        k.clear();
        memset(vis,0,sizeof vis);
        while(q--){
            int a,b,c,d;cin>>a>>b>>c>>d;
            k[{a,b}].push_back({c,d});
        }
        bfs();
    }
    return 0;
}