#include <stdio.h>

int   m,n,mx,my,flag[305][305],tag;

char  str[305][305];

struct node {
       int  x;
       int  y;
       int  count;
       }st[10000];
       
int   front,rear;

int bfs(int px,int py)
{
    int  i,j,x,y;
    tag=0;
    front=rear=-1;
    rear++;
    st[rear].x=px;
    st[rear].y=py;
    st[rear].count=0;
    while (front<=rear)
    {
          front=(front+1)%10000;
          x=st[front].x;
          y=st[front].y;
          if (x==mx && y==my)
          {
             tag=1;
             return   st[front].count;
          }
          for (i=-1;i<=1;i++)
              for (j=-1;j<=1;j++)
                  if ((i==0&&j!=0)||(i!=0&&j==0))
                      if ((x+i>=0)&&(y+j>=0)&&(x+i<m)&&(y+j<n)&&(flag[x+i][y+j]!=-1))
                      {
                           rear++;
                           st[rear].x=x+i;
                           st[rear].y=y+j;
                           if (flag[x+i][y+j]==0)   st[rear].count=st[front].count+1;
                           if (flag[x+i][y+j]==1)   st[rear].count=st[front].count+2;
                           flag[x+i][y+j]=-1;
                      }
    }
}

int main()
{
    int  i,j,tx,ty,co;
    while (scanf ("%d%d",&m,&n)!=EOF&&m&&n)
    {
          for (i=0;i<m;i++)
          {
              getchar();
              for (j=0;j<n;j++)
              {
                  scanf ("%c",&str[i][j]);
                  if (str[i][j]=='R'||str[i][j]=='S')   flag[i][j]=-1;
                  if (str[i][j]=='Y')
                  {
                      tx=i;
                      ty=j;
                      flag[i][j]=-1;
                  }
                  if (str[i][j]=='T')
                  {
                      mx=i;
                      my=j;
                      flag[i][j]=0;
                  }
                  if (str[i][j]=='E')  flag[i][j]=0;
                  if (str[i][j]=='B')  flag[i][j]=1;
              }
          }
          co=bfs(tx,ty);
          if (tag==1)        printf ("%d\n",co);
          else            printf ("-1\n");
    }
    return 0;
}

• Re:用bfs有什么需要注意的地方吗？？我用的bfs，怎么是超时呢？ (25) czcomt 2008-10-29 01:31:48