2470. Robot in Maze ，一道宽度搜索的经典题目，但是小弟我的一直是WA，请大家帮忙看看

2470. Robot in Maze ，一道宽度搜索的经典题目，但是我的一直是WA，请大家帮忙看看
原题网址：http://acm.tju.edu.cn/toj/showp2470.html
题意：S到T的最短路径，但是行走过程中改变方向的话步数要加1，输出最小步数，不能到达输出-1；

测试数据：
Sample Input
2
5 5
#####
#...#
#.#.#
#S#T#
#####
4 5
#.#.#
#.#.#
#S#T#
#####

Sample Output
8
-1


以下是我的代码：

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

struct node{
  int x,y;
  int step;
  char fx;
  };
char map[110][110];
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int num[120];

int n,m;
int sx,sy,dx,dy;
bool flag;
node f;
int k1;
int bfs()
{
  int i,j,k;
  int tx,ty;
  char temp;
  int sstep;
  queue<node>q;
  node front,rear;
  while(!q.empty())q.pop();
  q.push(f);
  while(!q.empty())
  {
  front=q.front();
  q.pop();
  if(front.x==dx&&front.y==dy){
  num[k1++]=front.step;
  flag=1;
  }
  map[front.x][front.y]='#';
  for(i=0;i<4;i++)
  {
  tx=front.x+dir[i][0];
  ty=front.y+dir[i][1];
  if(dir[i][0]==-1&&dir[i][1]==0)temp='n';
  if(dir[i][0]==1&&dir[i][1]==0)temp='s';
  if(dir[i][0]==0&&dir[i][1]==1)temp='e';
  if(dir[i][0]==0&&dir[i][1]==-1)temp='w';
  if(front.fx!=temp)sstep=front.step+2;
  else sstep=front.step+1;
  if(tx<0||tx>=m||ty<0||ty>=n||map[tx][ty]=='#')continue;
  rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=temp;
  map[tx][ty]='#';
  q.push(rear);
  }
  } 
  return 0;
}
   
   
int main()
{
  int t,i,j,k;
  scanf("%d",&t);
  while(t--)
  {
  scanf("%d%d",&m,&n);
  for(i=0;i<m;i++)
  for(j=0;j<n;j++)
  {
  cin>>map[i][j];
  if(map[i][j]=='S')
  {
  sx=i;
  sy=j;
  }
  if(map[i][j]=='T')
  {
  dx=i;
  dy=j;
  }
  }
  flag=0;
  f.x=sx;f.y=sy;
  f.step=0;f.fx='n';
  memset(num,99999,sizeof(num));
  k1=0;
  bfs();
  if(flag==0)printf("-1\n");
  if(flag==1){
  int min=99999;
  for(i=0;i<k1;i++)
  if(num[k1]<min)min=num[i];
  printf("%d\n",min);
  }
   
  }
  return 0;
}  
   
   


[解决办法]
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};

char map[101][101];
int visit[101][101][4];

int dx,dy,n,m;
struct node{
int x,y,step,fx;

};
queue<node>q;
node front,rear;

int bfs(int sx,int sy)
{
int tx,ty,tf,i,j,sstep;
front.x=sx;front.y=sy;front.step=0;front.fx=0;
while(!q.empty())q.pop();
q.push(front);
while(!q.empty())
{
front=q.front();
q.pop();
if(front.x==dx&&front.y==dy)
return front.step;
for(i=0;i<4;i++)
{
tx=front.x+dir[front.fx][0];
ty=front.y+dir[front.fx][1];
tf=front.fx;
if(tx>=0&&tx<n&&ty>=0&&ty<m&&map[tx][ty]!='#'&&!visit[tx][ty][tf])
{
sstep=front.step+1;
rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=front.fx;
visit[tx][ty][tf]=1;
q.push(rear);
}
//turn left
tx=front.x;
ty=front.y;
tf=(front.fx+1)%4;
if(!visit[tx][ty][tf])
{
sstep=front.step+1;
rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=tf;
visit[tx][ty][tf]=1;
q.push(rear);
}
//turn right
tx=front.x;
ty=front.y;
tf=(front.fx+3)%4;
if(!visit[tx][ty][tf])
{
sstep=front.step+1;
rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=tf;
visit[tx][ty][tf]=1;
q.push(rear);
}
}
}

 return -1;
}

int main()
{
int t,i,j,sx,sy;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S'){
sx=i;
sy=j;
}
if(map[i][j]=='T'){
dx=i;
dy=j;
}
}

memset(visit,0,sizeof(visit));
visit[sx][sy][0]=1;
printf("%d\n",bfs(sx,sy));
}
return 0;
}