首页 > 代码库 > CodeForces 676D Theseus and labyrinth

CodeForces 676D Theseus and labyrinth

最短路。

$dis[i][j][k]$记录到点$(i,j)$,门的状态为$k$时的最短路。转移的时候有$8$种方案,即直接走向周围四个点,或者进行旋转。比较烦的是判断两个相邻的点在状态$k$下是否连通,仔细一些就可以了。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c=getchar(); x=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-0; c=getchar();}}const int INF=0x7FFFFFFF;const int maxn=1010;int n,m,sx,sy,ex,ey;char s[maxn][maxn];int dir[4][2]={ {-1,0},{1,0},{0,-1},{0,1} };int dis[maxn][maxn][4];bool f[maxn*maxn*4];int tmp[5],tt[5],p1[5],p2[5];struct X{    int st,dis;    X(int ST,int DIS){ st=ST; dis=DIS;}    bool operator <(const X&a) const    {        return dis>a.dis;    }};bool p(int x,int y){    if(x<0||x>=n) return 0;    if(y<0||y>=m) return 0;    if(s[x][y]==*) return 0;    return 1;}void get(int a,int b,int st){    memset(tmp,0,sizeof tmp);    memset(tt,0,sizeof tt);    if(s[a][b]==+) tmp[0]=1,tmp[1]=1,tmp[2]=1,tmp[3]=1;    else if(s[a][b]==-) tmp[1]=1,tmp[3]=1;    else if(s[a][b]==|) tmp[0]=1,tmp[2]=1;    else if(s[a][b]==^) tmp[0]=1;    else if(s[a][b]==>) tmp[1]=1;    else if(s[a][b]==v) tmp[2]=1;    else if(s[a][b]==<) tmp[3]=1;    else if(s[a][b]==U) tmp[1]=1,tmp[2]=1,tmp[3]=1;    else if(s[a][b]==R) tmp[0]=1,tmp[2]=1,tmp[3]=1;    else if(s[a][b]==D) tmp[0]=1,tmp[1]=1,tmp[3]=1;    else if(s[a][b]==L) tmp[0]=1,tmp[1]=1,tmp[2]=1;    for(int i=0;i<4;i++) tt[(i+st)%4]=tmp[i];}bool check(int x1,int y1,int x2,int y2,int st){    get(x1,y1,st); for(int i=0;i<4;i++) p1[i]=tt[i];    get(x2,y2,st); for(int i=0;i<4;i++) p2[i]=tt[i];    if(x1==x2)    {        if(y1+1==y2)        {            if(p1[1]==1&&p2[3]==1) return 1;            return 0;        }        else        {            if(p1[3]==1&&p2[1]==1) return 1;            return 0;        }    }    else if(y1==y2)    {        if(x1+1==x2)        {            if(p1[2]==1&&p2[0]==1) return 1;            return 0;        }        else        {            if(p1[0]==1&&p2[2]==1) return 1;            return 0;        }    }    return 0;}void spfa(){    for(int i=0;i<n;i++)        for(int j=0;j<m;j++)            for(int k=0;k<4;k++)                dis[i][j][k]=INF;    dis[sx][sy][0]=0;    priority_queue<X>Q; Q.push(X(sx*m+sy,0));    while(!Q.empty())    {        X top=Q.top(); Q.pop();        int st,r,c,h=top.st;        st=h/(n*m); h=h-st*(n*m); r=h/m; c=h%m;        if(dis[r][c][st]<top.dis) continue;        for(int i=0;i<4;i++)        {            int t=(st+i)%4;            if(dis[r][c][st]+i<dis[r][c][t])            {                dis[r][c][t]=dis[r][c][st]+i;                Q.push(X(r*m+c+t*n*m,dis[r][c][t]));            }        }        for(int i=0;i<4;i++)        {            int tx=r+dir[i][0],ty=c+dir[i][1];            if(p(tx,ty)==0) continue;            if(check(r,c,tx,ty,st)==0) continue;            if(dis[r][c][st]+1<dis[tx][ty][st])            {                dis[tx][ty][st]=dis[r][c][st]+1;                Q.push(X(tx*m+ty+st*n*m,dis[tx][ty][st]));            }        }    }}int main(){    scanf("%d%d",&n,&m);    for(int i=0;i<n;i++) scanf("%s",s[i]);    scanf("%d%d",&sx,&sy); sx--; sy--;    scanf("%d%d",&ex,&ey); ex--; ey--;    spfa();    int ans=INF;    for(int i=0;i<4;i++) ans=min(ans,dis[ex][ey][i]);    if(ans==INF) printf("-1\n");    else printf("%d\n",ans);    return 0;}

 

CodeForces 676D Theseus and labyrinth