hdu1180 诡异的楼梯 bfs

题目链接：http://icpc.njust.edu.cn/Problem/Hdu/1180/

题目和不同的bfs有个不同的地方就是存在横着的或者竖着的楼梯，楼梯每过一个时刻就改变一次横竖的走向，人可以通过楼梯到达楼梯另一端的位置而只花费1的时间。所以我们只要在遇到楼梯的位置查看楼梯当前的走向，判断和人的横竖方向是否相同就行，相同则花费1时间，不同则花费2时间。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 #define maxn 25

 int n,m,t;

 int sx,sy,tx,ty;

 int dir[][]={,,-,,,,,-};//横向与纵向

 bool vis[maxn][maxn];

 char Map[maxn][maxn];

 struct node{

     int x,y,step;

     node(int x,int y,int s):x(x),y(y),step(s){}

     node(){}

     friend bool operator < (node a,node b)

     {

         return a.step>b.step;//由于优先队列是以最大为顶，所以就反向定义操作符使得最小step为顶

     }

 };

 node cur,nxt;

 bool ok(node a)

 {

     return a.x>&&a.x<=n&&a.y>&&a.y<=m&&Map[a.x][a.y]!='*'&&!vis[a.x][a.y];

 }

 int bfs()

 {

     mem(vis,false);

     priority_queue<node>q;

     q.push(node(sx,sy,));

     vis[sx][sy]=;

     while(!q.empty())

     {

         cur=q.top();

         q.pop();

         if(cur.x==tx&&cur.y==ty)

         {

             return cur.step;

         }

         f(i,,)

         {

             nxt=cur;

             nxt.x+=dir[i][];

             nxt.y+=dir[i][];

             nxt.step++;

             if(nxt.x<||nxt.x>n||nxt.y<||nxt.y>m||Map[nxt.x][nxt.y]=='*')continue;

             if(vis[nxt.x][nxt.y])continue;

             if(Map[nxt.x][nxt.y]=='|'||Map[nxt.x][nxt.y]=='-')//只要有楼梯就经过的原则，不放过任何一种状态

             {

                 char c=Map[nxt.x][nxt.y];//注意不能改变Map[cur.x][cur.y]的值，要让它保持原来的状态

                 if(nxt.step&)//步数为奇数时需要变换楼梯

                 {

                     if(c=='|')c='-';

                     else c='|';

                  }

                 nxt.x+=dir[i][];

                 nxt.y+=dir[i][];

                 if((c=='|'&&(i<=))||(c=='-'&&(i>)))//横向走时楼梯是纵向或者纵向走时楼梯是横向

                 {

                     nxt.step++;

                 }

                 if(!ok(nxt))continue;

                 if(nxt.x<||nxt.x>n||nxt.y<||nxt.y>m||Map[nxt.x][nxt.y]=='*')continue;

                 if(vis[nxt.x][nxt.y])continue;//每次状态(位置）改变时都要查询访问记录

             }

             vis[nxt.x][nxt.y]=;//注意每次一种状态入队都要设置访问记录

             q.push(nxt);

         }

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         f(i,,n)

             f(j,,m)

             {

                 scanf(" %c",&Map[i][j]);

                 if(Map[i][j]=='S')sx=i,sy=j;

                 if(Map[i][j]=='T')tx=i,ty=j;

             }

         pf("%d\n",bfs());

     }

  }