bfs-hdu1180-诡异的楼梯
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1180
题目大意：一个走迷宫问题， 求到达出口的最短时间，典型的bfs问题。不过迷宫中有会变方向的桥，如果通过楼梯走了两个格但是时间却还是一分钟。也就是走楼梯可以让你走的更快，是一个捷径。
由于楼梯方向是会变化的，需要判断是否可以通过楼梯，这与走的方向和此时楼梯的方向有关。如果两个方向相同，就可以通过。
人走的方向可以通过 dir[4][2]= {1,0, 0,1, -1,0, 0,-1} 判断，值得注意的是（1,0）并不是向右，而是向下，由于在记录迷宫的时候是从第一行、第二行、第三行这样一行一行记录的，这就导致坐标并不是数学中xy坐标系那样。
因此dir[4][2]= {1,0, 0,1, -1,0, 0,-1}的方向应该是下右上左。
代码中q是变化后的状态，如果a[q.x][q.y]=='|'，并且(q.step-1)%2==0，那么楼梯还是竖直的，（q.step-1）是走楼梯前的时间，即p.step 。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int sx,sy,m,n,ans;
char a[20][20],ch;
bool vis[20][20];
int dir[4][2]= {1,0, 0,1, -1,0, 0,-1}; //下右上左
struct node
{
int x,y,step;
};
int check(node p)
{
if(p.x>=0 && p.x<m && p.y>=0 && p.y<n && !vis[p.x][p.y]) //没有出界并且没有访问过
return 1;
else return 0;
}
int stair(node q,int i)
{
if((a[q.x][q.y]=='-' && i%2==1 && (q.step-1)%2==0) || //楼梯开始时横着，人左右走，此时楼梯仍横着
(a[q.x][q.y]=='-' && i%2==0 && (q.step-1)%2==1) || //楼梯开始时横着，人上下走，此时楼梯旋转成竖着
(a[q.x][q.y]=='|' && i%2==0 && (q.step-1)%2==0) || //楼梯开始时竖着，人上下走，此时楼梯仍竖着
(a[q.x][q.y]=='|' && i%2==1 && (q.step-1)%2==1) ) //楼梯开始时竖着，人左右走，此时楼梯旋转成横着
return 1;
else return 0;
}
void bfs()
{
queue <node> Q;
node p,q;
p.x = sx;
p.y = sy;
p.step = 0;
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
for(int i=0; i<4; i++)
{
q.x = p.x + dir[i][0];
q.y = p.y + dir[i][1];
q.step = p.step + 1;
if(check(q) && a[q.x][q.y]!='*')
{
if(a[q.x][q.y]=='T')
{
ans = q.step;
return;
}
if(a[q.x][q.y]=='.')
{
vis[q.x][q.y] = true;
Q.push(q);
}
if(a[q.x][q.y]=='-' || a[q.x][q.y]=='|')
{
if(stair(q,i))
{
q.x = q.x + dir[i][0];
q.y = q.y + dir[i][1];
if(check(q) && a[q.x][q.y]!='*')
{
if(a[q.x][q.y]=='T')
{
ans = q.step;
return;
}
vis[q.x][q.y] = true;
Q.push(q);
}
}
else
{
q = p;
q.step++;
Q.push(q);
}
}
}
}
}
}
int main()
{
while(cin>>m>>n)
{
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
{
cin>>ch;
a[i][j] = ch;
if(ch == 'S')
{
sx = i;
sy = j;
}
}
memset(vis,0,sizeof(vis));
vis[sx][sy] = true;
bfs();
cout<<ans<<endl;
}
return 0;
}
学着别人写的优先队列，后来发现好像每次放入新的元素时，队列中step都是越来越大的，没有step小的元素在step大的元素的后面这种情况，也就不需要每次排序了。以上代码就是直接把优先队列改成普通队列的，优先队列就比普通队列多个重载运算符“<”，把front（）改成top（），声明priority_queue就好了。
一开始走楼梯时写成了遇见楼梯就一定要走，能直接走肯定就走了，不能直接走就再加一分钟（一开始走到楼梯时就加了一分钟，现在再加一分钟，就是直接加了两分钟）然后直接把走后的状态放入队列，这样其实是不可以的。因为用这样一种情况存在，当你在等这一分钟的时候，有可能从别的路刚好到达了你走楼梯后的地方，这样其实是不走这个楼梯的路更快。但是如果按遇到这个楼梯需要等待，直接加两分钟，然后走楼梯后的这个地方已经被标记走过，真正快的路反而走不了。
因此在等楼梯变方向的这个情况，一定要把等楼梯的元素放入队列（加一分钟），不能把等完楼梯之后的状态（x，y是走楼梯后的，时间直接加两分钟）放入队列。
如果按上述一定走楼梯写可能也是AC，但是在自己胡乱验证的时候发现有的测试是通不过的，这也算是一个漏洞吧。