离散化 anoi2005穿越磁场 bzoj1967

今天下午太洋务了。。。

最近做题特别不顺，各种被水题卡。。。

这个题卡了快一个小时。。

上午被卡的题还没调呢。。。

这个题嘛。。。首先就是要离散化

这个题有助于深刻的理解离散化的本质和左右

具体的见这里

看完这个东西基本上就完全理解离散化了，不过理解到应用还是有差距的。。。

首先我们考虑如果不离散化的话，对于平面上的每个整点进行操作，从一个整点向上下左右四个整点连边，如果跨越的话权就是1，否则就是0

那么这个图就建好了

但是最后你会发现其实很多边权是0 的边是没有必要的，因为矩形实在是太少了！！！！

所以这个时候就要用离散化了，最后套一个最短路就可以了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAX 100010
#define rep(i,j,k) for(int i=j;i<=k;i++)

using namespace std;

int n,m,tot=0,size_x,size_y,value[2*MAX],to[2*MAX],head[MAX],next[2*MAX];
const int Dx[]={0,-1,1,0,0},Dy[]={0,0,0,-1,1};
int va[300][300],vb[300][300],q[2*MAX],dx[MAX],dy[MAX];
int sx,sy,tx,ty,t=0;
int d[MAX];

struct wbsr
{
	int x1,y1,x2,y2;
}a[1010];

void make(int X,int Y,int xx,int yy)
{
	t++;
	a[t].x1=X;
	a[t].y1=Y;
	a[t].x2=xx;
	a[t].y2=yy;
	dx[X]=dx[xx]=1;
	dy[Y]=dy[yy]=1;
}

inline void add(int from,int To,int weight)
{
	tot++;
	to[tot]=To;
	value[tot]=weight;
	next[tot]=head[from];
	head[from]=tot;
}

int calc(int x0,int y0,int x1,int y1,int cas)
{
	if(cas==1)
		return vb[x0][y0-1];
	if(cas==2)
		return vb[x0+1][y0-1];
	if(cas==3)
		return va[x0][y0-1];
	if(cas==4)
		return va[x0][y0];
}

inline void bfs(int s,int t)
{
	int l,r;
	memset(d,-1,sizeof(d));
	q[l=r=(size_x+1)*(size_y+1)]=s;
	d[s]=0;
	while(l<=r)
	{
		int now=q[l++];
		for(int i=head[now];i!=-1;i=next[i])
			if(d[to[i]]==-1)
			{
				if(value[i])
					d[to[i]]=d[now]+1,q[++r]=to[i];
				else
					d[to[i]]=d[now],q[--l]=to[i];
				if(to[i]==t)
					return;
			}
	}
	return ;
}

int main()
{
	memset(next,-1,sizeof(next));
	scanf("%d",&n);
	for(int i=1,a1,a2,a3;i<=n;i++)
		scanf("%d%d%d",&a1,&a2,&a3),make(a1,a2,a1,a2+a3),make(a1,a2,a1+a3,a2),make(a1+a3,a2,a1+a3,a2+a3),make(a1,a2+a3,a1+a3,a2+a3),dx[a1]=dx[a1+a3]=dy[a2]=dy[a2+a3]=1;
	scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
	dx[sx]=dx[tx]=1;
	dy[sy]=dy[ty]=1;
	size_x=size_y=1;
	rep(i,0,20000)
	{
		if(dx[i])
			dx[i]=++size_x;
		if(dy[i])
			dy[i]=++size_y;
	}
	rep(i,1,t)
		a[i].x1=dx[a[i].x1],a[i].x2=dx[a[i].x2],a[i].y1=dy[a[i].y1],a[i].y2=dy[a[i].y2];
	sx=dx[sx];
	tx=dx[tx];
	sy=dy[sy];
	ty=dy[ty];
	rep(i,1,t)
	{
		for(int j=a[i].x1;j<a[i].x2;j++)
			va[j][a[i].y1]=va[j][a[i].y2]=1;
		for(int j=a[i].y1;j<a[i].y2;j++)
			vb[a[i].x1][j]=vb[a[i].x2][j]=1;
	}
	size_x++,size_y++;
	rep(i,1,size_x)
		rep(j,1,size_y)
			rep(k,1,4)
			{
				int now_x=i+Dx[k],now_y=j+Dy[k];
				if(now_x<1||now_y<1||now_x>size_x||now_y>size_y)
					continue;
				int z=calc(i,j,now_x,now_y,k);
				add((i-1)*size_y+j,(now_x-1)*size_y+now_y,z);
			}
	bfs((sx-1)*size_y+sy,(tx-1)*size_y+ty);
	printf("%d\n",d[(tx-1)*size_y+ty]);
	return 0;
}

离散化 anoi2005穿越磁场 bzoj1967,布布扣,bubuko.com

离散化 anoi2005穿越磁场 bzoj1967

原文：http://blog.csdn.net/wbysr/article/details/22521143