ZOJ3865:Superbot(BFS) The 15th Zhejiang University Programming Contest

一个有几个小坑的bfs

题目很长，但并不复杂，大概总结起来有这么点。

有t组输入

每组输入n, m, p。表示一个n*m的地图，每p秒按键会右移一次（这个等会儿再讲）。

然后是地图的输入。其中'@'为起点，'$'为终点，'.'为通路，'*'为不通。

问从起点到终点最少需要多久？

一眼看去，裸的bfs嘛，10*10的地图，简单！

不过还是连错4次……

注意！

每一秒有4种操作，注意，不是三种，1. 光标左移，2. 光标右移，3. 按照光标方向行走，4. 不动（尤其是这一个）。

所谓光标左移，右移，因为题目中给出了光标（在图上，共4个方向），每次改变的移动方向只能是当前光标选择的方向的左右两个。而行走只能按照光标所指的方向。

另外每过p秒，方向会变化（初始四个方向的顺序为左右上下，p秒后变成右上下左，再过p秒后变为上下左右）。

废话说完，上代码——

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int N = ;

 struct node

 {

     int x, y, dis, step;

 };

 int go[][] = {{, -}, {, }, {-, }, {, }};

 int t;

 int n, m, P;

 char mp[N][N];

 bool v[N][N];

 bool vv[N][N][];

 int change(int a)

 {

     switch(a)

     {

     case :

         return ;

     case :

         return ;

     case :

         return ;

     case :

         return ;

     }

 }

 void bfs()

 {

     node p;

     bool k = ;

     for(int i = ; i < n; i++)

     {

         for(int j = ; j < m; j++)

         {

             if(mp[i][j] == '@')

             {

                 p.x = i;

                 p.y = j;

                 k = ; break;

             }

         }

         if(k) break;

     }

     p.dis = ;

     p.step = ;

     vv[p.x][p.y][] = ;

     queue<node> que;

     que.push(p);

     while(!que.empty())

     {

         node p = que.front();

         que.pop();

         int xx = p.x+go[p.dis][];

         int yy = p.y+go[p.dis][];

         if(xx >=  && xx < n && yy >=  && yy < m)

         {

             if(v[xx][yy] == )

             {

                 if(mp[xx][yy] == '.')

                 {

                     v[xx][yy] = ;

                     node q;

                     q.x = xx;

                     q.y = yy;

                     q.step = p.step+;

                     q.dis = p.dis;

                     if(q.step%P == )

                     {

                         q.dis = change(q.dis);

                         vv[xx][yy][q.dis] = ;

                     }

                     que.push(q);

                 }

                 else if(mp[xx][yy] == '$')

                 {

                     printf("%d\n", p.step+);

                     return;

                 }

             }

         }

         if((p.step+)%P == ) {p.dis = change(p.dis);}

         node q;

         q.x = p.x;

         q.y = p.y;

         q.step = p.step+;

         q.dis = p.dis+;

         q.dis %= ;

         if(vv[q.x][q.y][q.dis] == )

         {

             que.push(q);

             vv[q.x][q.y][q.dis] = ;

         }

         q.dis = p.dis+;

         q.dis %= ;

         if(vv[q.x][q.y][q.dis] == )

         {

             que.push(q);

             vv[q.x][q.y][q.dis] = ;

         }

         q.dis = p.dis;

         if(vv[q.x][q.y][q.dis] == )

         {

             que.push(q);

             vv[q.x][q.y][q.dis] = ;

         }

     }

     printf("YouBadbad\n");

 }

 int main()

 {

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

     scanf("%d", &t);

     while(t--)

     {

         memset(mp, , sizeof(mp));

         memset(v, , sizeof(v));

         memset(vv, , sizeof(vv));

         scanf("%d%d%d", &n, &m, &P);

         for(int i = ; i < n; i++)

         {

             scanf("%s", mp[i]);

         }

         bfs();

     }

 }

巴特西

ZOJ3865:Superbot(BFS) The 15th Zhejiang University Programming Contest

最新文章

热门文章