题解 | #maze#

题目考点：bfs + 优先队列
题目概述：每张地图有起点、终点、陷阱、传送门，求最短时间。注意情况有以下几种：起点有陷阱、传送门终点有陷阱、坐传送门还不如走过去时间短等。前两种问题用数组标记即可；第三种情况用优先队列维护，保证不管是坐传送门还是不开启传送门，到达该点的时间是划算的

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define tb std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll n, m, t;
ll a1, a2, b1, b2;
char map[310][1010];
ll  smap[1010][1010];
ll dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
struct poss{
    ll x, y, step;
    ll xj, yj;
};
//小根堆优先队列自定义比较器
struct cmp{
    bool operator ()(const poss &x, const poss &y)
    {
        if(x.step >= y.step)return 1;
        return 0;
    }
};
//使用优先队列
priority_queue<poss, vector<poss>, cmp> r;
int main()
{
    //tb;
    poss s, next;
    while(cin>>n>>m>>t){
        ll flag = 0, findt = 0;
        memset(smap, 0, sizeof(smap));
        while(!r.empty())r.pop();
        //输入地图
        for(ll i = 1; i <= n; i++)cin>>map[i];
        //处理传送门
        while(t--){
            cin>>a1>>a2>>b1>>b2;
            a1 += 1; a2 += 1; b1 += 1; b2 += 1;
            if(map[a1][a2] == '#'||map[b1][b2] == '#')continue;
            s.x  = a1; s.y  = a2;
            s.xj = b1; s.yj = b2; s.step = 1e9;
            smap[a1][a2] = -1;
            r.push(s);
        }
        //寻找起点并进入队列
        for(ll i = 1; i <= n; i++)
        for(ll j = 1; j <= m; j++)
            if(map[i][j] == 'S'){s.x = i; s.y = j; s.step = 0; r.push(s);}
        //bfs大法
        while(!r.empty()){
            if(findt) break;
            s = r.top();
            //四个方向拓展
            for(ll i = 0; i < 4; i++){
                next.x = s.x + dir[i][0];
                next.y = s.y + dir[i][1];
                //找到就返回
                if(map[next.x][next.y] == 'T'){
                    cout<<s.step + 1<<'\n';
                    flag = 1; findt = 1; break;
                }
                //有传送门且开启(就是将出口入队)
                if(smap[next.x][next.y] == -1){
                    next.x = s.xj; next.y = s.yj; next.step = s.step + 3;
                    if(!smap[next.x][next.y] || smap[next.x][next.y] > next.step)
                        r.push(next), smap[next.x][next.y] = next.step;
                }
                //没有传送门或者有传送门但没开启
                next.step = s.step + 1;
                if(!smap[next.x][next.y] || smap[next.x][next.y] > next.step)
                if(next.x > 0 && next.x <= n && next.y > 0 && next.y <=m && map[next.x][next.y] != '#')
                    r.push(next), smap[next.x][next.y] = next.step;
            }
            r.pop();
        }
        if(!flag)cout<<"-1\n";
    }
    return 0;
}