自动搬运

查看原文

来自洛谷，原作者为

	D_14134 AFOing。。。

搬运于2025-08-24 21:38:47，当前版本为作者最后更新于2019-09-18 09:29:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有一个简单的想法。直接判断两个点所属的不同的矩形的数量。

最开始一直不知道问题出在哪儿，后来借鉴了题解的图。

可以看出，题目的坑点在于无法沿边线走。

正解：我们可以通过数据发现，n非常小，只有100。那么我们先离散化。然后在离散化后的图中在两点之间连边。没有跨过磁场的边权为0，跨过磁场的边权为1。然后跑spfa就可以了。

不过离散化的时候需要注意一些小问题。不能直接把第一个出现和最后一个出现的横坐标和纵坐标看成是边界，因为磁场是没有边界的，它有可能从外面绕一大圈过去，并不穿过磁场。 还有就是要注意离散化的时候不要把一些能通过的地方变成不能通过的了，比如说本来两条边中间有路可走结果处理成了两条边相邻，也不能把原来不能走的地方处理成能走的了。

code

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 510
using namespace std;

struct node{
	int a,b,c,d;
}s[maxn];

int n,x,y,l,A,B,C,D;
int xx,yy,cntx,cnty,X[maxn*2],Y[maxn*2],xp[maxn*2],yp[maxn*2],lshx[maxn*2],lshy[maxn*2];
int tot,point[maxn*maxn],nxt[maxn*maxn*10],v[maxn*maxn*10],c[maxn*maxn*10],dis[maxn*maxn];
bool flag[maxn][maxn][2],vis[maxn*maxn];
queue<int> q;

int cmpx(int x,int y){
	return X[x]<X[y];
}

int cmpy(int x,int y){
	return Y[x]<Y[y];
}

void add(int x,int y,int z){
	nxt[++tot]=point[x];point[x]=tot;v[tot]=y;c[tot]=z;
	nxt[++tot]=point[y];point[y]=tot;v[tot]=x;c[tot]=z;
}

void spfa(){
	int s=(A-1)*cnty+B;
	memset(dis,127,sizeof(dis)),dis[s]=0;
	memset(vis,0,sizeof(vis)),vis[s]=true;
	while(!q.empty()) q.pop();
	q.push(s);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		vis[now]=false;
		for(int i=point[now];i;i=nxt[i])
			if(dis[v[i]]>dis[now]+c[i]){
				dis[v[i]]=dis[now]+c[i];
				if(!vis[v[i]]){
					vis[v[i]]=true;
					q.push(v[i]);
				}
			}
	}
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&x,&y,&l);
		X[++xx]=x,xp[xx]=xx,X[++xx]=x+l,xp[xx]=xx;
		Y[++yy]=y,yp[yy]=yy,Y[++yy]=y+l,yp[yy]=yy;
	}
	scanf("%d%d%d%d",&A,&B,&C,&D);
	X[++xx]=A,xp[xx]=xx,X[++xx]=C,xp[xx]=xx;
	Y[++yy]=B,yp[yy]=yy,Y[++yy]=D,yp[yy]=yy;

	X[++xx]=-1,xp[xx]=xx,Y[++yy]=-1,yp[yy]=yy;
	X[++xx]=10000,xp[xx]=xx,Y[++yy]=10000,yp[yy]=yy;
}

void lsh(){
	sort(xp+1,xp+xx+1,cmpx);sort(yp+1,yp+yy+1,cmpy);
	for(int i=1;i<=xx;++i){
		if(X[xp[i]]!=X[xp[i-1]]) ++cntx,lshx[xp[i]]=++cntx;
		else lshx[xp[i]]=cntx;
	}
	for(int i=1;i<=yy;++i){
		if(Y[yp[i]]!=Y[yp[i-1]]) ++cnty,lshy[yp[i]]=++cnty;
		else lshy[yp[i]]=cnty;
	}
	xx=yy=0;
	for(int i=1;i<=n;++i){
		s[i].a=lshx[++xx],s[i].b=lshx[++xx];
		s[i].c=lshy[++yy],s[i].d=lshy[++yy];
	}
	A=lshx[++xx],C=lshx[++xx],B=lshy[++yy],D=lshy[++yy];
}

int main(){
	init();
	lsh();
	for(int i=1;i<=n;++i){
		int a=s[i].a,b=s[i].b,c=s[i].c,d=s[i].d;
		for(int j=a;j<b;++j) flag[j][d][0]=flag[j][c][0]=1;
		for(int j=c;j<d;++j) flag[a][j][1]=flag[b][j][1]=1;
	}
	for(int i=1;i<=cntx;++i)
		for(int j=1;j<=cnty;++j){
			int r=(i-1)*cnty+j,t;
			if(!flag[i][j][0]){
				t=i*cnty+j;
				if(flag[i][j][1]) add(r,t,1);
				else add(r,t,0);
			}
			if(!flag[i][j][1]){
				t=(i-1)*cnty+j+1;
				if(flag[i][j][0]) add(r,t,1);
				else add(r,t,0);
			}
		}
	spfa();
	int t=(C-1)*cnty+D;
	printf("%d\n",dis[t]);
}