TOJ–2470:Robot Maze (BFS)

1. 题目源地址：http://acm.tju.edu.cn/toj/showp2470.html

2. 源代码

（1）先给出一个别人的AC代码

//TJU Exam 2006_2470:Robot Maze    机器人从起点走到目的地，利用 BFS求最短步数 
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int visited[101][101][4];//因为一共有 4个方向，故第三个参数为 4 
char map[101][101];
int x,y,m,n;

struct
{
   int x,y;
}ext[4]={{-1,0},{0,1},{1,0},{0,-1}};//分别代表 4个方向 ：上下左右 

struct
{   
   int x,y,l,r;
}q[40001];//x,y,l,r 分别代表 x坐标，y坐标，距离起点的步数，方向

int BFS()
{
   int i,j,top;
   int xt,yt,rt;
   memset(visited,0,sizeof(visited));
   //以下六行为初始化顶点
   top=0;
   q[top].x=x;
   q[top].y=y;
   q[top].r=0;
   q[top].l=0;
   visited[x][y][q[top++].r]=1;
   
   for(i=0;i<top;i++)
   {
      rt=q[i].r;
      xt=q[i].x+ext[rt].x;//只有直走的时候 x,y的坐标才会改变，并且和 rt（即方向）联系起来
      yt=q[i].y+ext[rt].y;
      
      if(xt>=0 && xt<m && yt>=0 && yt<n && map[xt][yt]!='#' && !visited[xt][yt][rt])
      {
         q[top].x=xt;
         q[top].y=yt;
         q[top].r=rt;
         q[top++].l=q[i].l+1;
         visited[xt][yt][rt]=1;
         if(map[xt][yt]=='T')   return q[top-1].l;//返回的是top-1的值哦  因为最后top都是++了的 
      } 
      
      rt=(q[i].r+1)%4;
      xt=q[i].x;
      yt=q[i].y;
      
      if(xt>=0 && xt<m && yt>=0 && yt<n && map[xt][yt]!='#' && !visited[xt][yt][rt])
      {
         q[top].x=xt;
         q[top].y=yt;
         q[top].r=rt;
         q[top++].l=q[i].l+1;
         visited[xt][yt][rt]=1;
      }
      
      rt=(q[i].r+3)%4;
      xt=q[i].x;
      yt=q[i].y;
      
      if(xt>=0 && xt<m && yt>=0 && yt<n && map[xt][yt]!='#' && !visited[xt][yt][rt])
      {
         q[top].x=xt;
         q[top].y=yt;
         q[top].r=rt;
         q[top++].l=q[i].l+1;
         visited[xt][yt][rt]=1;
      }
   } 
   return -1;
}

int main()
{
    int caseNum,i,j;
    cin>>caseNum;
    while(caseNum--)
    {
       cin>>m>>n;
       for(i=0;i<m;i++)
       {
          cin>>map[i];
          for(j=0;j<m;j++)
          {
             if(map[i][j]=='S')
             {
                x=i;
                y=j;
             } 
          }
          
       }
       cout<<BFS()<<endl;
    }
    return 0;
}
 

（2）自己写的队列实现BFS，测试样例都通过，还是WrongAnswer。。。不知道错在哪？

#include<iostream>
#include<queue>
#include<memory.h>
#include<stdio.h>
using namespace std;

char map[110][110];
int visited[110][110];
int dx[]={-1,0,1,0};//注意：上左下右  这里的i值用来判断之后的是否要加上旋转步数 
int dy[]={0,-1,0,1};
int M,N;

struct node
{
   int x,y;
   int step;
   int dir; //添加方向值，以判断是否需要加上旋转步数 
}start,end,current,next;

bool InMap(int x,int y)
{
   if(x>=1 && x<=M && y>=1 && y<=N)
      return true;
   else
      return false;
}

int BFS()
{
    int i,j;
    queue<node> Q;
    
    start.step=0;
    start.dir=0;
    visited[start.x][start.y]=1;
    Q.push(start);
    
    while(!Q.empty())
    {
       current=Q.front();
       Q.pop();
       
       for(i=0;i<4;i++)
       {
          next.x=current.x+dx[i];
          next.y=current.y+dy[i];
          next.step=current.step+1;
          
          next.dir=i%2;//初始化时上下方向的dir=0,水平方向的dir=1。此处利用dx,dy数组的定义来获得next.dir 
          
          if((next.dir && !current.dir) || (!next.dir && current.dir))//由水平转向竖直方向或者由竖直转向水平方向时，step还要加1 
            next.step++;
          
           if(next.x==end.x && next.y==end.y)
                return next.step;
                
          if(!visited[next.x][next.y] && InMap(next.x,next.y) && map[next.x][next.y]!='#')
          {
             visited[next.x][next.y]=1;
             Q.push(next);
          }
       } 
    }
    return -1;
}


int main()
{
    int caseNum;
    int i,j;
    cin>>caseNum;
    while(caseNum--)
    {
        cin>>M>>N;
        getchar();
        memset(visited,0,sizeof(visited));
        
        for(i=1;i<=M;i++)
           for(j=1;j<=N;j++)
           {
              cin>>map[i][j];
              if(map[i][j]=='S')
              {
                 start.x=i;
                 start.y=j;
              }
              else if(map[i][j]=='T')
              {
                 end.x=i;
                 end.y=j;
              } 
           }


        int ans=BFS();
        
        if(ans!=-1)   cout<<ans<<endl;
        else          cout<<-1<<endl;
     
    }
    return 0;
}