hdoj1372

题目连接:acm.hdu.edu.cn/showproblem.php?pid=1372
bfs题,其实就是8×8的棋盘上有一只马,问它从指定格点跳到另一指定格点最少需要跳几次。第一次做bfs题,开始的时候不知道怎么记录深度(跳了几次)。后来终于想到了,只要给队列增加一个depth域,每个格点入队时记录它的depth即可。起始格点的depth=0.如果queue[i]是由queue[j]扩展出来的,则queue[i].depth=queue[j]+1;

#include<stdio.h>
#include<stdlib.h>
int a[9],b[9];
typedef struct Node{
	int x;
	int y;
	int depth;
}node;
int main()
{
	a[1]=-1;
	b[1]=-2;
	a[2]=-2;
	b[2]=-1;
	a[3]=-2;
	b[3]=1;
	a[4]=-1;
	b[4]=2;
	a[5]=1;
	b[5]=2;
	a[6]=2;
	b[6]=1;
	a[7]=2;
	b[7]=-1;
	a[8]=1;
	b[8]=-2;
	int x1,x2,y1,y2;
	char c1,c2;
	int iq=0;
	while(scanf("%c%d %c%d",&c1,&x1,&c2,&x2)!=EOF)
	{
		getchar();
		if(c1==c2 && x1==x2)
		{
			printf("To get from %c%d to %c%d takes %d knight moves.\n",c1,x1,c2,x2,0);
			continue;
		}
		iq=0;
		node queue[65];
		int visit[9][9]={0},x,y;
		bool flag=false;
		y1=c1-'a'+1;
		y2=c2-'a'+1;
		visit[x1][y1]=true;
		queue[iq].x=x1;
		queue[iq].y=y1;
		queue[iq++].depth=0;
		int j;
		int count=0;
		for(j=0;j<=iq-1;j++)
		{
			for(int i=1;i<=8;i++)
				if(queue[j].x+a[i]>=1 && queue[j].x+a[i]<=8 && queue[j].y+b[i]>=1 && queue[j].y+b[i]<=8 && !visit[queue[j].x+a[i]][queue[j].y+b[i]])
				{
					visit[queue[j].x+a[i]][queue[j].y+b[i]]=true;
					queue[iq].x=queue[j].x+a[i];
					queue[iq].y=queue[j].y+b[i];
					queue[iq++].depth=queue[j].depth+1;
					if(queue[iq-1].x==x2 && queue[iq-1].y==y2)
					{
						flag=true;
						break;
					}

				}
				if(flag)
					break;
		}
		printf("To get from %c%d to %c%d takes %d knight moves.\n",c1,x1,c2,x2,queue[iq-1].depth);
	
	}
//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>