2312.txt

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

#define debug 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 100000
#ifdef debug
	#define NMAX 400
#else 
	#define NMAX 302
#endif
int a[NMAX][NMAX];
int flag[NMAX][NMAX];
int map[NMAX][NMAX];
int M,N;
typedef struct 
{
	int y;
	int x;
}DATA;
DATA que[NMAX*NMAX*10];
int front,end;

int xp[4]={0,1,0,-1},yp[4]={-1,0,1,0};
int min;
int stx,sty,edx,edy;

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 init()
{
	for(int i=end-front/2;i>0;--i)
		HeapAdjust(i,end-front);
}
void minque()
{
	DATA t;
	t=que[end];
	que[end]=que[front];
	que[front]=t;
	HeapAdjust(1,end-1);
}
	
	
void solve()
{
	front=end=1;
	a[sty][stx]=0;
	flag[sty][stx]=0;
	enque(sty,stx);
	int cy,cx;
//	init();
	while(deque(cy,cx))
	{
		flag[cy][cx]=1;
		for(int p=0;p<4;p++)
		{
			if(a[cy+yp[p]][cx+xp[p]]>a[cy][cx]+map[cy+yp[p]][cx+xp[p]]&&map[cy+yp[p]][cx+xp[p]]!=-1)
			{
				a[cy+yp[p]][cx+xp[p]]=a[cy][cx]+map[cy+yp[p]][cx+xp[p]];
				enque(cy+yp[p],cx+xp[p]);

			}
		}

//		minque();
	}
				
}
void input()
{
	char str[400];
	memset(a,0,sizeof(a));
	memset(flag,0,sizeof(flag));
	memset(map,0xff,sizeof(map));
	int i,j;
	for(i=1;i<=M;i++)
	{
		for(j=1;j<=N;j++)
		{
			a[i][j]=INF;
		}
	}

	for(i=1;i<=M;i++)
	{
		scanf("%s",str);
		for(j=1;j<=N;j++)
		{
			switch(str[j-1])
			{
			case 'Y':sty=i;stx=j;map[i][j]=1;break;
			case 'T':edy=i;edx=j;map[i][j]=1;break;
			case 'S':map[i][j]=INF;break;
			case 'B':map[i][j]=2;break;
			case 'R':map[i][j]=INF;break;
			case 'E':map[i][j]=1;break;
			}
		}
	}
}

main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d%d",&M,&N);
	while(M)
	{
		input();
		solve();
		if(edy==sty&&edx==sty)
			printf("0\n");
		if(a[edy][edx]==INF)
			printf("-1\n");
		else
			printf("%d\n",a[edy][edx]);
		scanf("%d%d",&M,&N);
	}

	


#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}