NC15665 maze

优先队列\(BFS\)裸题

const int N=310;
char g[N][N];
int dist[N][N];
bool vis[N][N];
map<PII,PII> mp;
PII st,ed;
int n,m,q;
 
inline bool check(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<m;
}
 
int bfs(int x,int y)
{
    memset(dist,0x3f,sizeof dist);
    memset(vis,0,sizeof vis);
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    heap.push({0,x*m+y});
    dist[x][y]=0;
 
    while(heap.size())
    {
        int t=heap.top().se;
        heap.pop();
 
        int x=t/m,y=t%m;
         
        if(x == ed.fi && y == ed.se) return dist[x][y];
        if(vis[x][y]) continue;
        vis[x][y]=true;
 
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(!check(a,b) || g[a][b] == '#') continue;
            if(dist[a][b] > dist[x][y]+1)
            {
                dist[a][b]=dist[x][y]+1;
                heap.push({dist[a][b],a*m+b});
            }
            if(g[a][b] == 'O')
            {
                int na=mp[{a,b}].fi,nb=mp[{a,b}].se;
                if(dist[na][nb] > dist[x][y]+3)
                {
                    dist[na][nb]=dist[a][b]+3;
                    heap.push({dist[na][nb],na*m+nb});
                }
            }
        }
    }
    return -1;
}
 
int main()
{
    while(cin>>n>>m>>q)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                scanf(" %c",&g[i][j]);
                if(g[i][j] == 'S') st={i,j};
                if(g[i][j] == 'T') ed={i,j};
            }
 
        mp.clear();
        while(q--)
        {
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            if(g[a][b] == '#' || g[c][d] == '#') continue;
            g[a][b]='O';
            mp[{a,b}]={c,d};
        }
 
        int t=bfs(st.fi,st.se);
        cout<<t<<endl;
    }
 
    //system("pause");
}