2243.txt

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

#define debug 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 10000
#ifdef debug
	#define NMAX 10
#else 
	#define NMAX 1001
#endif
int a[13][13];
int flag[13][13];
typedef struct 
{
	int y;
	int x;
}DATA;
DATA que[100];
int front,end;


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

int enque(int y,int x)
{
	que[end].y=y;
	que[end].x=x;
	end++;
	return 1;
}
int deque(int &y,int &x)
{
	if(front==end)
		return 0;
	y=que[front].y;
	x=que[front].x;
	front++;
	return 1;
}
solve()
{
	front=end=0;
	a[sty][stx]=0;
	flag[sty][stx]=1;
	enque(sty,stx);
	int cy,cx;
	while(deque(cy,cx))
	{
		for(int p=0;p<8;p++)
		{
			if(a[cy+yp[p]][cx+xp[p]]&&flag[cy+yp[p]][cx+xp[p]]==0)
			{
				a[cy+yp[p]][cx+xp[p]]=a[cy][cx]+1;
				flag[cy+yp[p]][cx+xp[p]]=1;
				enque(cy+yp[p],cx+xp[p]);
			}
		}
	}
				
}

main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	char str1[3],str2[3];
	
	while(scanf("%s %s",str1,str2)!=EOF)
	{
		memset(a,10000,sizeof(a));
		memset(flag,0,sizeof(flag));
		for(int i=0;i<13;i++)
		{
			a[i][0]=a[i][1]=a[i][10]=a[i][11]=0;
			a[0][i]=a[1][i]=a[10][i]=a[11][i]=0;
		}
		stx=str1[0]-'a'+2;
		sty=str1[1]-'1'+2;
		edx=str2[0]-'a'+2;
		edy=str2[1]-'1'+2;
		if(stx==edx&&sty==edy)
		{
			printf("To get from %s to %s takes 0 knight moves.\n",str1,str2);
			continue;
		}
		solve();
		printf("To get from %s to %s takes %d knight moves.\n",str1,str2,a[edy][edx]);
		
		
		
	}


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