maze

题意：走迷宫，有传送阵，移动花费1秒，传送花费3秒，求到达终点的最短时间。

思路：最短路问题，首先想到的是Dijkstra算法，但是题目数据不大，建图起来麻烦（其实不会），所以我们直接用bfs跑一便就行了，一个多了几个传送阵的迷宫问题，丢进优先队列里搜索时特判一下就行了，一些细节的说明在代码上有注释说明了。

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
int n,m,q,i,j,sx,sy,ex,ey;
char a[305][305];//地图
int xx[]={1,-1,0,0},yy[]={0,0,1,-1};//方向数组
int vis[305][305];//1为可访问，0为不可访问
struct Hi{
    int x,y,step;
    bool operator<(const Hi & ano) const {//重写堆方法
        return step > ano.step;
    }
};
Hi convey[305][305];//传送门
priority_queue<Hi>que;
void bfs(){
    while(!que.empty()){
        que.pop();//注意清空队列
    }
    vis[sx][sy]=0;
    que.push((Hi){sx,sy,0});
    while(!que.empty()){
        int nowx=que.top().x;
        int nowy=que.top().y;
        int nowt=que.top().step;
        if(nowx==ex && nowy==ey){//找到直接return
            printf("%d\n",nowt);
            return;
        }
        que.pop();
        if(convey[nowx][nowy].step==1 && vis[convey[nowx][nowy].x][convey[nowx][nowy].y]){//判断当前点是否为有效传送点
            que.emplace((Hi){convey[nowx][nowy].x,convey[nowx][nowy].y,nowt+3});
        }
        for(i=0;i<4;i++){
            int dx=xx[i]+nowx;
            int dy=yy[i]+nowy;
            if(a[dx][dy]!='#' && vis[dx][dy]!=0){//可行路
                que.emplace((Hi){dx,dy,nowt+1});
                vis[dx][dy]=0;//这里说明一下：如果新的点是通过上下左右一步直接走到的，可以标记掉，因为是附近的。
                              //可如果是传送门过去的就不要标记了，因为传送门过去的不一定最优，可能还是远路呢。
            }
        }
    }
    printf("-1\n");
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&q)!=EOF){
        memset(a,'\0',sizeof(a));
        memset(convey,0,sizeof(convey));
        memset(vis,0,sizeof(vis));
        for(i=0;i<n;i++){
            scanf("%s",a[i]);
            for(j=0;j<m;j++){
                if(a[i][j]=='S'){
                    sx=i;
                    sy=j;
                }
                else if(a[i][j]=='T'){
                    ex=i;
                    ey=j;
                }
                vis[i][j]=1;//地图可行区域为1
            }
        }
        while(q--){
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            convey[x1][y1].x=x2;
            convey[x1][y1].y=y2;
            if(a[x2][y2] != '#')//传送终点没有陷阱
                convey[x1][y1].step=1;//step在该数组中1表示可行，0表示不可行
        }
        bfs();
    }


}