每日一题 5月14日 maze bfs+优先队列

题目链接：https://ac.nowcoder.com/acm/problem/15665
题目大意：

思路：如果没有传送门我们直接bfs就可以了。如果用传送门那么用一个优先队列以时间排序就可以了，取保出队时一定是到达此处的花费的最少时间。

#include<bits/stdc++.h>
using namespace std;

char s[305][305];
int id[305][305];
int vis[305][305];
int xx[4]={0, 1, 0, -1};
int yy[4]={1, 0, -1, 0};
int tot=0, sx, sy, tx, ty;
int n, m, Q, x, y, w, z;
struct node{
    int x, y, t;
};
vector<node> v[1005];
struct ru{
    int operator()(const node &a, const node &b){
        return a.t>b.t;
    }
};

priority_queue<node, vector<node>, ru> q;
int DFS(int sx, int sy){
    q.push(node{sx, sy, 0});
    while(!q.empty()){
        node t=q.top(); q.pop();
        if(vis[t.x][t.y]){//不优化会RE
            continue;
        }
        if(t.x==tx&&t.y==ty){
            return t.t;
        }
        vis[t.x][t.y]=1;
        for(int k=0; k<4; k++){
            int x=t.x+xx[k], y=t.y+yy[k];
            if(vis[x][y]==0&&x<n&&x>=0&&y<m&&y>=0&&s[x][y]!='#'){
                q.push(node{x, y, t.t+1});
            }
        }
        for(auto x: v[id[t.x][t.y]]){
            //cout<<x.x<<" "<<x.y<<" "<<x.t<<" "<<v[id[t.x][t.y]].size()<<endl;
            if(vis[x.x][x.y]==0&&s[x.x][x.y]!='#'){
                q.push(node{x.x, x.y, t.t+3});
            }
        }

    }
    return -1;
}

int main(){

    while(~scanf("%d%d%d%*c", &n, &m, &Q)){
        tot=0;
        while(!q.empty()){
            q.pop();
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                s[i][j]=getchar();
                if(s[i][j]=='S'){
                    sx=i, sy=j;
                }
                if(s[i][j]=='T'){
                    tx=i, ty=j;
                }
                id[i][j]=vis[i][j]=0;
            }
            getchar();
        }
        for(int i=1; i<=Q; i++){
            scanf("%d%d", &x, &y);
            if(id[x][y]==0){
                id[x][y]=++tot;
            }
            scanf("%d%d", &w, &z);
            v[id[x][y]].push_back(node{w, z, 0});
        }
        cout<<DFS(sx, sy)<<endl;
        for(int i=1; i<=Q; i++){
            v[i].clear();
        }
    }


    return 0;
}