题解 P2208 【[USACO13OPEN]重力异常What's Up With Gra…】

Adove · 2018-09-28 14:21:42 · 题解

这题可以通过构建分层图的方式解决

构建两个图，分别是重力向上的和重力向下的

对于重力某种情况下可以反转重力的位置，在该位置向另一张图连权为1的单向边

对于某种重力状况下可以向左或向右的位置，向左或向右连0边

跑最短路，在终点的两种情况下取最短距离即可

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1005;

int n,m,np,S,T;
int ln[MAXN*MAXN<<1],h[MAXN*MAXN<<1];
int q[MAXN*MAXN<<2];
bool vis[MAXN*MAXN<<1];
bool c[MAXN][MAXN];
struct rpg{
    int li,nx,ln;
}a[MAXN*MAXN<<2];

int get(int x,int y){return (x-1)*m+y;}
void add(int ls,int nx,int ln){a[++np]=(rpg){h[ls],nx,ln};h[ls]=np;}

void SPFA(int S)
{
    memset(ln,0x7f,sizeof(ln));
    int hd=1,tl=1;q[hd]=S;ln[S]=0;vis[S]=1;
    while(hd<=tl){
        int nw=q[hd++];vis[nw]=0;
        for(int i=h[nw];i;i=a[i].li){
            if(ln[a[i].nx]>ln[nw]+a[i].ln){
                ln[a[i].nx]=ln[nw]+a[i].ln;
                if(!vis[a[i].nx]){
                    vis[a[i].nx]=1;
                    q[++tl]=a[i].nx;
                }
            }
        }
    }return;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            char ch;cin>>ch;
            if(ch=='#'){c[i][j]=1;continue;}
            else if(ch=='C') S=get(i,j);
            else if(ch=='D') T=get(i,j);
        }
    }for(int i=2;i<n;++i){
        for(int j=1;j<=m;++j){
            if(!c[i][j]){
                if(!c[i+1][j]) add(get(i,j),get(i+1,j),0);
                if(!c[i-1][j]) add(get(i,j)+n*m,get(i-1,j)+n*m,0);
                if(c[i+1][j]){
                    if(j<m&&!c[i][j+1]) add(get(i,j),get(i,j+1),0);
                    if(j>1&&!c[i][j-1]) add(get(i,j),get(i,j-1),0);
                }if(c[i-1][j]){
                    if(j<m&&!c[i][j+1]) add(get(i,j)+n*m,get(i,j+1)+n*m,0);
                    if(j>1&&!c[i][j-1]) add(get(i,j)+n*m,get(i,j-1)+n*m,0);
                }
            }
        }
    }for(int i=1;i<=m;++i){
        if(!c[1][i]&&!c[2][i]) add(i,i+m,0);
        if(!c[n][i]&&!c[n-1][i])add(get(n,i)+n*m,get(n-1,i)+n*m,0);
    }for(int i=2;i<n;++i){
        for(int j=1;j<=m;++j){
            if(!c[i][j]){
                if(c[i+1][j]) add(get(i,j),get(i,j)+n*m,1);
                if(c[i-1][j]) add(get(i,j)+n*m,get(i,j),1);
            }
        }
    }SPFA(S);if(min(ln[T],ln[T+n*m])<2e9)
    printf("%d\n",min(ln[T],ln[T+n*m]));
    else puts("-1");
    return 0;
}