2049.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define INF 30000
#define NMAX 201
int a[NMAX][NMAX];
int map[NMAX][NMAX][4];
int yp[4]={1,0,-1,0},xp[4]={0,1,0,-1};
int M,N;
int x,y,d,t;
void init()
{
	for(int i=0;i<=200;i++)
	{
		map[0][i][2]=-1;
		map[200][i][0]=-1;
		map[i][0][3]=-1;
		map[i][200][1]=-1;
	}
}
typedef struct 
{
	int y,x;
}DATA;
DATA que[NMAX*NMAX*100];
long front,end;
int enque(int y,int x)
{
	que[end].y=y;
	que[end].x=x;
	end++;
	return 1;
}
void HeapAdjust(int s,int m);
int deque(int &y,int &x)
{
	HeapAdjust(1,end-1);
	if(front==end)
	{
		y=0;
		x=0;
		return 0;
	}
	y=que[front].y;
	x=que[front].x;
	end--;
	DATA t;
	t=que[end];
	que[end]=que[front];
	que[front]=t;
	
	return 1;
}
void HeapAdjust(int s,int m)
{
	DATA rc;
	rc.x=que[s].x;
	rc.y=que[s].y;
	for(int j=2*s;j<=m;j*=2)
	{
		if(j<m&&a[que[j].y][que[j].x]>a[que[j+1].y][que[j+1].x])
			++j;
		if(a[rc.y][rc.x]<=a[que[j].y][que[j].x])
			break;
		que[s]=que[j];
		s=j;
	}
	que[s].x=rc.x;
	que[s].y=rc.y;
}

void set(int v)
{
	int i;
	if(d==0)
	{
		for(i=x;i<x+t;i++)
		{
			map[y][i][2]=v;
			map[y-1][i][0]=v;
		}
	}
	else
	{
		for(i=y;i<y+t;i++)
		{
			map[i][x][3]=v;
			map[i][x-1][1]=v;
		}
	}
}
void solve()
{
	front=end=0;
	enque(0,0);
	a[0][0]=0;
	int cy,cx,p;
	while(deque(cy,cx))
	{
		for(p=0;p<4;p++)
		{
			if(map[cy][cx][p]!=-1)
			{
				if(a[cy+yp[p]][cx+xp[p]]>map[cy][cx][p]+a[cy][cx]||a[cy+yp[p]][cx+xp[p]]==-1)
				{
					a[cy+yp[p]][cx+xp[p]]=map[cy][cx][p]+a[cy][cx];
					enque(cy+yp[p],cx+xp[p]);
				}
			}
		}
		
	}

}	
int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i;
	float ex,ey;
	scanf("%d%d",&M,&N);
	while(M!=-1)
	{
		memset(map,0,sizeof(map));
		memset(a,0xff,sizeof(a));
		init();
		for(i=0;i<M;i++)
		{	
			scanf("%d%d%d%d",&x,&y,&d,&t);
			set(-1);
		}
		for(i=0;i<N;i++)
		{	
			scanf("%d%d%d",&x,&y,&d);
			t=1;
			set(1);
		}
		scanf("%f%f",&ex,&ey);
		if(ex>=200||ey>=200)
		{
			printf("0\n");
		}
		else
		{
			solve();
			if(a[(int)ey][(int)ex]!=-1)
				printf("%d\n",a[(int)ey][(int)ex]);
			else
				printf("-1\n");
		}
		scanf("%d%d",&M,&N);
	}
		
#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}