maze

题意：在一个n x m个格子组成的迷宫，'#'表示的格子不能走，'.'表示可以走。起点用'S'表示，目的地用'T'表示。只能向上下左右相邻的格子移动，每移动一次花费1秒。有q个单向传送阵，每个传送阵各有一个入口和一个出口，在入口处，你可以选择是否传送，传送过程会花费3秒；
注意：一个格子可能既有多个入口，又有多个出口。
请求出到达目的地的最短时间？

思路：用优先队列写bfs

代码：

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int n, m, q, dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

char s[505][505];

vector<int> g[100005];//记录传送阵，用一个整数表示位置，整数=x*300+y;

struct state
{
    int x, y;
}st,en;

struct w
{
    int x, y, t;
}w, w1;

bool operator<(struct w a,struct w b)
{
    return a.t>b.t;
};

int f[305][305];

int bfs()
{
    memset(f,-1,sizeof(f));
    priority_queue<struct w> que;
    w.x=st.x;
    w.y=st.y;
    w.t=0;
    que.push(w);
    while(!que.empty())
    {
        w=que.top();
        que.pop();
        if(f[w.x][w.y]!=-1)
        {
            continue;
        }
        printf("%d %d %d\n",w.x,w.y,w.t);
        f[w.x][w.y]=w.t;
        if(w.x==en.x&&w.y==en.y)
        {
            return f[w.x][w.y];
        }
        for(int i=0;i<4;i++)
        {
            w1.x=w.x+dx[i];
            w1.y=w.y+dy[i];
            w1.t=w.t+1;
            if(w1.x>=0&&w1.x<n&&w1.y>=0&&w1.y<m&&f[w1.x][w1.y]==-1&&s[w1.x][w1.y]!='#')
            {
                que.push(w1);
            }
        }
        int v=w.x*300+w.y;
        for(int i=0;i<g[v].size();i++)
        {
            w1.x=g[v][i]/300;
            w1.y=g[v][i]%300;
            w1.t=w.t+3;
            if(w1.x>=0&&w1.x<n&&w1.y>=0&&w1.y<m&&f[w1.x][w1.y]==-1&&s[w1.x][w1.y]!='#')
            {
                que.push(w1);
            }
        }
    }
    return -1;
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&q))
    {
        for(int i=0;i<n;i++)
        {
            scanf("%s",s[i]);
        }
        for(int i=0;i<q;i++)
        {
            int x, y, x2, y2;
            scanf("%d%d%d%d",&x,&y,&x2,&y2);
            g[x*300+y].push_back(x2*300+y2);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(s[i][j]=='S')
                {
                    st.x=i;
                    st.y=j;
                }
                if(s[i][j]=='T')
                {
                    en.x=i;
                    en.y=j;
                }
            }
        }
        int z=bfs();
        printf("%d\n",z);
        for(int i=0;i<100005;i++)
        {
            g[i].clear();
        }
    }
    return 0;
}