题目链接

maze

题目思路

优先队列排列时间，bfs找最短时间

代码实现

#include<bits/stdc++.h>
using namespace std;
const int Max=301;
int n,m,q,sx,sy,ex,ey;
int mp[Max][Max],vis[Max][Max];
struct Node{
    int x,y,tm;
    bool operator < (const Node b) const{
        return tm>b.tm;
    }
};
int dr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int mark[Max][Max];
vector<Node> send[Max][Max];
//预处理
bool judge(Node a)
{
    if(vis[a.x][a.y])    return false;
    if(!mp[a.x][a.y])    return false;
    return true;
}

int bfs()
{
    priority_queue<Node> qu;
    qu.push(Node{sx,sy,0});
    vis[sx][sy]=1;
    while(!qu.empty())
    {
        Node tp=qu.top();
        qu.pop();
        if(tp.x==ex&&tp.y==ey)
            return tp.tm;
        if(mark[tp.x][tp.y])
        {
            for(int i=send[tp.x][tp.y].size()-1;i>=0;i--)
            {
                Node nx=send[tp.x][tp.y][i];
                if(judge(nx))
                {
                    nx.tm=tp.tm+3;
                    qu.push(nx);
                }
            }
        }
        for(int i=0;i<4;i++)
        {
            Node nx{tp.x+dr[i][0],tp.y+dr[i][1],tp.tm+1};
            if(judge(nx))
            {
                qu.push(nx);
                vis[nx.x][nx.y]=1;
            }
        }
    }
    return -1;
}
int main()
{
    while(cin>>n>>m>>q)
    {
        char c;
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        memset(mark,0,sizeof(mark));
        memset(send,0,sizeof(send));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>c;
                if(c=='.')    mp[i][j]=1;
                if(c=='S')    sx=i,sy=j,mp[i][j]=1;
                if(c=='T')    ex=i,ey=j,mp[i][j]=1;
            }
        int x1,y1,x2,y2;    
        for(int i=0;i<q;i++)
        {
            cin>>x1>>y1;
            x1++,y1++;
            mark[x1][y1]=1;
            cin>>x2>>y2;
            x2++,y2++;
            send[x1][y1].push_back(Node{x2,y2});
        }
        cout<<bfs()<<endl;
    }
    return 0;
}