#include<iostream>
#include<queue>
using namespace std;
#define maxN 310
int  m,n;
char a[maxN][maxN];
int  f[maxN][maxN];
int  dir[4][2] = {
	  -1, 0,
	   1, 0,
	   0,-1,
	   0, 1
};

typedef struct point
{
	int x;
	int y;
}point;

bool operator < (const point &p, const point &q) 
{
   return f[p.x][p.y] > f[q.x][q.y];
}

priority_queue<point> Q;

bool EnQueue(point &t)
{
   if(!Q.empty())
   {
	   t = Q.top();
	   Q.pop();
	   return true;
   }
   return false;
}
bool inner(point s, int r,int c)
{
	if(s.x>=0 && s.x<r && s.y>=0 && s.y<c)
		return true;
	else
		return false;
}
int BFS(point s)
{		
	int   i = 0;
	point here = s,nbr; 
	do{
       for(i = 0; i<4; i++)
	   {
		 nbr.x = here.x + dir[i][0];
         nbr.y = here.y + dir[i][1];
		 if( inner(nbr,m,n) 
			 && f[nbr.x][nbr.y] == 0 
			 && a[nbr.x][nbr.y] !='R' 
			 && a[nbr.x][nbr.y] !='S'
			 && a[nbr.x][nbr.y] !='Y')
		 {
			if(a[nbr.x][nbr.y] == 'B')
				f[nbr.x][nbr.y] = f[here.x][here.y] + 2;
			else if(a[nbr.x][nbr.y] == 'E')
				f[nbr.x][nbr.y] = f[here.x][here.y] + 1;
			else if(a[nbr.x][nbr.y] == 'T')
			    return f[here.x][here.y] + 1;
		    Q.push(nbr);
		 }
	   }
	   if(Q.empty())
		   return -1;
	   EnQueue(here);
	}while(1);
}

int main(void)
{
  int i,j;
  point s;
  while(EOF!=scanf("%d%d",&m,&n),m||n) // m row , n col
  {	  
     for(i=0;i<m;i++)
        scanf("%s",&a[i]);
     for(i=0;i<m;i++)
        for(j=0;j<n;j++)
		{
			if(a[i][j] == 'Y')
			{
				s.x = i;
			    s.y = j;
				goto solve;
			}
		}
solve:
	 memset(f,0,sizeof(f));	 
	 printf("%d\n",BFS(s));
  }
  return 0;
}

• Re:怎么wa了啊... (13) CydorniaKnight 2008-07-17 20:59:39
• Re:怎么wa了啊... (7) zhudonghui 2008-07-17 21:00:58