自动搬运

查看原文

来自洛谷，原作者为

	Adove 私者一时，公者千古

搬运于2025-08-24 21:35:09，当前版本为作者最后更新于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;
}