#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MIN(a,b)  ((a>b)?b:a)
short flag[500][500][3];//三种状态，0 代表直立，1代表向下躺，2代表向右躺
char plane[510][510];
struct queue
{
	short x,y;
	short stat;
	short step;
}q[85000];
int start[2][2],target[2];
int start_len,m,n;
int front,tail;
int move[3][4][3]={{{0,-2,1},{0,1,1},{-2,0,2},{1,0,2}},
{{0,-1,0},{0,2,0},{-1,0,1},{1,0,1}},{{0,-1,2},{0,1,2},{-1,0,0},{2,0,0}}};
void init()
{
	int i,j;
	memset(flag,0,sizeof(flag));
	memset(plane,'#',sizeof(plane));
	start_len=0;
	getchar();
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			plane[i][j]=getchar();
			if(plane[i][j]=='X')
			{
				start[start_len][0]=j;
				start[start_len++][1]=i;
			}
			if(plane[i][j]=='O')
			{
				target[0]=j;
				target[1]=i;
			}
		}
	//	plane[i][j]='\0';	
		getchar();
	}
}

void solve()
{
	front=0;
	int i,x,y,stat;
	if(start_len==1)
	{
		q[front].x=start[start_len-1][0];
		q[front].y=start[start_len-1][1];
		q[front].stat=0;
		q[front].step=1;
	}
	else 
	{
		if(start[start_len-2][0]==start[start_len-1][0])
		{
			q[front].x=start[start_len-2][0];
			q[front].y=MIN(start[start_len-1][1],start[start_len-2][1]);
			q[front].stat=1;
			q[front].step=1;
		}
		else
		{
			q[front].x=MIN(start[start_len-2][0],start[start_len-1][0]);
			q[front].y=start[start_len-2][1];
			q[front].stat=2;
			q[front].step=1;
		}
	}	
	flag[q[front].y][q[front].x][q[front].stat]=1;
	tail=1;
	flag[target[1]][target[0]][0]=(short)65536;
	while(front<tail)
	{
		x=q[front].x;
		y=q[front].y;
		stat=q[front].stat;
		if(q[front].x==target[0] && q[front].y==target[1] && q[front].stat==0 && flag[target[1]][target[0]][0]>q[front].step)
			flag[target[1]][target[0]][0]=q[front].step;
		for(i=0;i<4;i++)
		{
			if(move[stat][i][2]==0)
			{
				if((x+move[stat][i][0]>0 && x+move[stat][i][0]<n-1) && (y+move[stat][i][1]>0 && y+move[stat][i][1]<m-1))
				{
					if(plane[y+move[stat][i][1]][x+move[stat][i][0]]!='#' && plane[y+move[stat][i][1]][x+move[stat][i][0]]!='E')
					{
						if(flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]==0 || (flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]>(q[front].step+1)))
						{
							q[tail].x=x+move[stat][i][0];					
							q[tail].y=y+move[stat][i][1];
							q[tail].stat=move[stat][i][2];
   							q[tail++].step=q[front].step+1;
    						flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]=q[front].step+1;										
						}	
					}
				}
			}
			else if(move[stat][i][2]==1)
			{
				if((x+move[stat][i][0]>0 && x+move[stat][i][0]<n-1) && (y+move[stat][i][1]>0 && y+move[stat][i][1]<m-1))
				{
					if((y+move[stat][i][1]+1>0 && y+move[stat][i][1]+1<m-1))
					{
						if(plane[y+move[stat][i][1]][x+move[stat][i][0]]!='#')
						{
							if(plane[y+move[stat][i][1]+1][x+move[stat][i][0]]!='#')
							{
								if(flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]==0 || (flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]>(q[front].step+1)))
								{
									q[tail].x=x+move[stat][i][0];					
									q[tail].y=y+move[stat][i][1];
									q[tail].stat=move[stat][i][2];
									q[tail++].step=q[front].step+1;
									flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]=q[front].step+1;
								}	
							}
						}
					}
				}
			}
			else if(move[stat][i][2]==2)
			{
				if((x+move[stat][i][0]>0 && x+move[stat][i][0]<n-1) && (y+move[stat][i][1]>0 && y+move[stat][i][1]<m-1))
				{
					if((x+move[stat][i][0]+1>0 && x+move[stat][i][0]+1<n-1))
					{
						if(plane[y+move[stat][i][1]][x+move[stat][i][0]]!='#')
						{
							if(plane[y+move[stat][i][1]][x+move[stat][i][0]+1]!='#')
							{
								if(flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]==0 || (flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]>(q[front].step+1)))
								{
									q[tail].x=x+move[stat][i][0];					
									q[tail].y=y+move[stat][i][1];
									q[tail].stat=move[stat][i][2];
									q[tail++].step=q[front].step+1;
									flag[y+move[stat][i][1]][x+move[stat][i][0]][move[stat][i][2]]=q[front].step+1;
								}	
							}
						}
					}
				}
			}
		}
		front++;
	}
}
int main()
{
	//int step;	
	while(scanf("%d%d",&m,&n)!=EOF && (m+n)!=0)
	{
		init();
		if(m==3 && n==3)
		{
			printf("Impossible\n");
			continue;
		}
		if(start_len==2 &&( start[0][0]==target[0] && start[0][1]==target[1]))
		{
			printf("0\n");
			continue;
		}
		solve();
		if(flag[target[1]][target[0]][0]==0)
			printf("Impossible\n");
		else
			printf("%d\n",flag[target[1]][target[0]][0]-1);
	}
	return 0;
}

• 可能是你的P[]数组元素申请少了， (34) xidiansoul 2008-04-11 22:08:58
  • Re:可能是你的P[]数组元素申请少了， (62) heimengnan 2009-04-20 22:15:32