maze 题解

这道题，因为传送阵需要3s，所以，我们如果打普通的bfs可能会挂，于是，为了满足正确性，就可以类比01bfs之类的，搞个优先队列做。。。

但是，个人觉得有点麻烦，我们不妨从"这道题是一个搜索题"这个想法中解放出来，那么，这题就变成了一道明显的最短路问题啦！我们先利用网络图连边，然后再把传送阵的q条边添加进来就好辣！

因为有网格图，所以不建议打spfa（除非进行些玄学优化），剩下的就是dijkstra板子了！

（注意清空数组）

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=301,M=300*300*4+1001;
char a[N][N];
struct node{
    int v,w,nex;
}t[M];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool vis[N*N];int dis[N*N];
int las[N*N],len;
inline void add(int u,int v,int w){
    t[++len]=(node){v,w,las[u]},las[u]=len;
}
inline void dijkstra(int st){
    memset(dis,0x3f3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<pair<int,int> >sp;
    dis[st]=0;sp.push(make_pair(0,st));
    while(!sp.empty()){
        int x=sp.top().second;sp.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=las[x];i;i=t[i].nex){
            int v=t[i].v,w=t[i].w;
            if(dis[v]>dis[x]+w){
                dis[v]=dis[x]+w;
                sp.push(make_pair(-dis[v],v));
            }
        }
    }
}
int main(){
    int n,m,q;
    while(~scanf("%d%d%d",&n,&m,&q)){
        memset(las,0,sizeof(las)),len=0;
        int sx,sy,tx,ty;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                scanf(" %c",&a[i][j]);
                if(a[i][j]=='S'){
                    sx=i,sy=j;
                }
                if(a[i][j]=='T'){
                    tx=i,ty=j;
                }
            }
        }
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(a[i][j]!='#'){
                    for(int k=0;k<4;++k){
                        int x=i+dx[k],y=j+dy[k];
                        if(x&&x<=n&&y&&y<=m&&a[x][y]!='#'){
                            add((i-1)*m+j,(x-1)*m+y,1);
                        }
                    }
                }
            }
        }
        for(int i=1;i<=q;++i){
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            ++x1,++y1,++x2,++y2;
            add((x1-1)*m+y1,(x2-1)*m+y2,3);
        }
        dijkstra((sx-1)*m+sy);
        if(!vis[(tx-1)*m+ty]){
            puts("-1");
        }else{
            printf("%d\n",dis[(tx-1)*m+ty]);
        }
    }
    return 0;
}