/* Note:Your choice is C IDE */
#include "stdio.h"

int n,m,p,q;
int min[305][305];//记忆化DP：保存每一点的最小值
int zou[4][2]={ {0,1},{0,-1},{1,0},{-1,0} };
int turn[305][305];//记忆化保存每一点的耗时值
//算法：直接遍历耗时表，取最小值

typedef struct 
{
	int i,j;
}Q;
Q queue[90010];//注意队列的大少
	
int bfs(int x,int y)
{
	int x2,y2,z;
	int front,tail;
	
	front=tail=0;
	queue[0].i=x;
	queue[0].j=y;
	tail=1;
	
	min[x][y]=turn[x][y];//初始化起始点
	while(front!=tail)
	{
		x=queue[front].i;
		y=queue[front].j;
		front++;
		if(front==90010) front=0;//循环队列
		
		for(z=0;z<4;z++)
		{
			x2=x+zou[z][0];
			y2=y+zou[z][1];
			if( x2>=0 && x2<m && y2>=0 && y2<n )
			{
				//到达终点,就退出，这一步有问题
				/*if( x2==p && y2==q ) 	
				{
					min[p][q]=turn[x2][y2]+min[x][y];
					return 0; 
				}*/
				
		        //判断原地的值加上走后的值的大小情况
		        if( turn[x2][y2]+min[x][y] < min[x2][y2] ) 
			    {
			    	min[x2][y2]=turn[x2][y2]+min[x][y];//修改最小值
			    	queue[tail].i=x2;
					queue[tail].j=y2;
					tail++;
					if(tail==90010) tail=0;//循环队列
			    }
					
			}
		}
	}
	
	return 0;
}

int main()
{
	int i,j,a,b;
	char str[305];
	
	//freopen("2312.txt","r",stdin);
	while(1)
	{
		scanf("%d%d",&m,&n);
		if( n==0 && m==0 ) break;

		for(i=0;i<m;i++)
		{
			scanf("%s",str);
			for(j=0;j<n;j++)
			{
				turn[i][j]=10000;
				min[i][j]=10000;
				switch(str[j])
				{
					case 'Y':a=i;b=j;turn[i][j]=1;break;//一开始就要1
					case 'T':p=i;q=j;turn[i][j]=0;break;//终点的耗时为0
					case 'S': ;
					case 'R':break;
					case 'E':turn[i][j]=1;break;
					case 'B':turn[i][j]=2;break;//打墙壁耗时2
				}
			}
			//printf("%s\n",str);
		}
		
		bfs(a,b);//广度优先搜索
		if(min[p][q]==10000) printf("-1\n");
		else printf("%d\n",min[p][q]);
	}
	
    return 0;
}

• Re:为何多了一步到终点就退出，就会错误 (93) 320586 2010-07-11 20:16:59