#include<stdio.h>
typedef struct
{
	int x,y;
}POINT;
int main(void)
{
	int i,j,maze[5][5],used[5][5];
	int front,rear;
	POINT u,v,q[10000],path[5][5];
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			used[i][j]=0;
			scanf("%d",&maze[i][j]);
		}
	}
	front=rear=0;
	q[0].x=q[0].y=0;
	used[0][0]=1;
	path[0][0].x=path[0][0].y=0;
	while(front<=rear)
	{
		u.x=q[front].x;
		u.y=q[front].y;
		front++;
		if(u.x==4&&u.y==4)
			break;
		if(!used[u.x+1][u.y]&&maze[u.x+1][u.y]!=1&&u.x+1<=4)
		{
			++rear;
			q[rear].x=u.x+1;
			q[rear].y=u.y;
			used[u.x+1][u.y]=1;
			path[u.x+1][u.y].x=u.x;
			path[u.x+1][u.y].y=u.y;
		}
		if(!used[u.x][u.y+1]&&maze[u.x][u.y+1]!=1&&u.y+1<=4)
		{
			++rear;
			q[rear].x=u.x;
			q[rear].y=u.y+1;
			used[u.x][u.y+1]=1;
			path[u.x][u.y+1].x=u.x;
			path[u.x][u.y+1].y=u.y;
		}
	}
	u.x=u.y=4;
	while(u.x!=0||u.y!=0)
	{
		printf("(%d, %d)\n",4-u.x,4-u.y);
		v.x=path[u.x][u.y].x;
		v.y=path[u.x][u.y].y;
		u.x=v.x;
		u.y=v.y;
	}
	printf("(4, 4)\n");
	return 0;
}

• Re:BFS版本 (86) hewo 2012-05-15 11:36:40