http://acm.hdu.edu.cn/showproblem.php?pid=1180
注意点就是楼梯是在harry移动完之后才会改变方向,那么只要统计到达这个点时间奇偶性，就可以知道当前楼梯是水平的还是垂直的。
并且我们需要知道当前到达楼梯这个点的方向,这样才知道下一个往哪个方向走,可以根据dir数组来判断方向。
楼梯不用判重。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std; char field[][];
int dir[][]={{,},{-,},{,},{,-}};
int n,m;
struct point
{
int x,y,time;
bool operator < (const point a) const
{
return time>a.time;
}
};
point s,e; bool check(point t)
{
if(s.x>=&&s.x<n&&s.y>=&&s.y<m&&field[s.x][s.y]!='*')
return true;
return false;
} int bfs()
{
priority_queue<point>que;
que.push(s);
field[s.x][s.y]='*';
while(que.size())
{
point t=que.top(); que.pop(); if(t.x==e.x&&t.y==e.y) return t.time;
for(int i=;i<;i++)
{
s=t;
s.x=t.x+dir[i][];
s.y=t.y+dir[i][];
if(check(s))
{
if(field[s.x][s.y]=='|')
{
//printf("%d %d %d %d %d\n",dir[i][0],dir[i][1],t.x,t.y,t.time);
if(s.time%==) //偶数 那么 还是 '|'
{
if(dir[i][]!=) //如果是垂直方向只要1分钟就可以到达
{
s.x+=dir[i][];
// printf("%d %d %d\n",s.x,s.y,s.time);
if(!check(s)) continue;
s.time+=;
// printf("%d %d %d\n",s.x,s.y,s.time);
field[s.x][s.y]='*';
que.push(s);
}
else //是水平方向，就要等2秒 因为要等一秒
{
s.y+=dir[i][];
if(!check(s)) continue;
s.time+=;
field[s.x][s.y]='*';
que.push(s);
}
}
else //奇数 那么变成了 '-' 下面同理
{
if(dir[i][]!=)
{
s.x+=dir[i][];
// printf("%d %d %d\n",s.x,s.y,s.time);
if(!check(s)) continue;
s.time+=;
// printf("%d %d %d\n",s.x,s.y,s.time);
field[s.x][s.y]='*';
que.push(s);
}
else
{
s.y+=dir[i][];
if(!check(s)) continue;
s.time+=;
field[s.x][s.y]='*';
que.push(s);
}
}
}
else if(field[s.x][s.y]=='-')
{
if(s.time%==)
{
if(dir[i][]!=)
{
s.x+=dir[i][];
if(!check(s)) continue;
s.time+=;
field[s.x][s.y]='*';
que.push(s);
}
else
{
s.y+=dir[i][];
if(!check(s)) continue;
s.time+=;
field[s.x][s.y]='*';
que.push(s);
}
}
else
{
if(dir[i][]!=)
{
s.x+=dir[i][];
if(!check(s)) continue;
s.time+=;
field[s.x][s.y]='*';
que.push(s);
}
else
{
s.y+=dir[i][];
if(!check(s)) continue;
s.time+=;
field[s.x][s.y]='*';
que.push(s);
}
}
}
else
{
s.time+=;
field[s.x][s.y]='*';
que.push(s);
}
}
}
}
}
int main()
{
//freopen("a.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
getchar();
for(int i=;i<n;i++)
{
scanf("%s",field[i]);
// printf("%s\n",field[i]);
for(int j=;j<m;j++)
{
if(field[i][j]=='S')
{
s.x=i;
s.y=j;
s.time=;
}
else if(field[i][j]=='T')
{
e.x=i;
e.y=j;
}
}
}
printf("%d\n",bfs());
}
return ;
}