hdoj1242——bfs

有的格子停留2 unit times,那么只需对应入队时深度+2即可。
进一步:如果题目中有的格子停留时间不定,则只需入队时根据条件将自己入队即可。

#include<stdio.h>
#include<stdlib.h>
typedef struct Point{
	int x;
	int y;
	int depth;
}Point;
int a[5],b[5];
int main()
{
	int n,m;
	a[1]=-1,b[1]=0;
	a[2]=0,b[2]=-1;
	a[3]=1,b[3]=0;
	a[4]=0,b[4]=1;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		getchar();
		char map[210][210];
		int i,j,k;
		int visit[210][210];
		Point queue[50000];
		int iq=0;
		int xs,ys;
		for(i=0;i<=n+1;i++)
			for(j=0;j<=m+1;j++)
				visit[i][j]=1;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%c",&map[i][j]);
				if(map[i][j]=='.'||map[i][j]=='x'||map[i][j]=='r')
					visit[i][j]=0;
				if(map[i][j]=='a')
				{
					visit[i][j]=0;
					xs=i;
					ys=j;
				}
			}
			getchar();
		}
		visit[xs][ys]=1;
		queue[iq].x=xs;
		queue[iq].y=ys;
		queue[iq++].depth=0;
		bool flag=false;
		for(i=0;i<iq;i++)
		{
			int curx=queue[i].x;
			int cury=queue[i].y;
			for(j=1;j<=4;j++)
			{
				if(!visit[curx+a[j]][cury+b[j]])
				{
					queue[iq].x=curx+a[j];
					queue[iq].y=cury+b[j];
					queue[iq++].depth=map[curx+a[j]][cury+b[j]]=='x'?queue[i].depth+2:queue[i].depth+1;
					visit[curx+a[j]][cury+b[j]]=1;
					if(map[curx+a[j]][cury+b[j]]=='r')
					{
						flag=true;
						break;
					}
				}
			}
			if(flag)
				break;
		}
		if(flag)
			printf("%d\n",queue[iq-1].depth);
		else
			printf("Poor ANGEL has to stay in the prison all his life.\n");
	}
//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>