Hdu 5336 XYZ and Drops (bfs 模拟)

题目链接：

题目描述：

　　有一个n*m的格子矩阵，在一些小格子里面可能会有一些水珠，每个小水珠都有一个size。现在呢，游戏开始咯，在一个指定的空的小格子里面有一个将要向四周爆裂的水珠，在下一面分别向上，下，左，右四个方向发射一个小水滴，（小水滴与水珠同，小水滴没有size），当小水滴走向一个格子，这个格子如果是空或者有其他的小水滴同时走到这个格子的情况下，对小水滴的运动轨迹是不影响的。但是遇到水珠的话，小水滴就会被吸收，水珠每次吸收一个小水滴size会增加1。为了万物的平衡，水珠size大于4的话就会向四周爆裂成为小水滴。问T时间后每个水珠的状态。

解题思路：

　　就是bfs模拟一下小水滴运动的状态就ok了，比赛的时候一直卡题意。

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

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

 struct node

 {//坐标，运动方向，运动时间

     int x, y, dir, t;

 };

 int maps[][maxn][maxn], point[maxn][];

 int r, c, x, y, t;

 void bfs ()

 {

     queue <node> Q;

     node p, q;

     p.x = x;

     p.y = y;

     p.dir = ;

     p.t = ;

     Q.push (p);

     while (!Q.empty())

     {

         p = Q.front ();

         Q.pop ();

         if (p.t >= t)

             return ;

         if (p.dir == )

         {

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

             {

                 q.x = p.x + dir[i][];

                 q.y = p.y + dir[i][];

                 q.dir = i;

                 q.t = p.t + ;

                 if (>=q.x||q.x>r || >=q.y||q.y>c)

                     continue;

                 if (maps[][q.x][q.y] == q.t)

                     continue;

                 if ( !maps[][q.x][q.y] )

                     Q.push (q);

                 else

                 {

                     maps[][q.x][q.y] ++;

                     if (maps[][q.x][q.y] > )

                     {

                         maps[][q.x][q.y] = q.t;

                         maps[][q.x][q.y] = ;

                         q.dir = ;

                         Q.push (q);

                     }

                 }

             }

         }

         else

         {

             q.x = p.x + dir[p.dir][];

             q.y = p.y + dir[p.dir][];

             q.dir = p.dir;

             q.t = p.t + ;

              if (>=q.x||q.x>r || >=q.y||q.y>c)

                     continue;

              if (maps[][q.x][q.y] == q.t)

                     continue;

              if ( !maps[][q.x][q.y] )

                     Q.push (q);

                 else

                 {

                     maps[][q.x][q.y] ++;

                     if (maps[][q.x][q.y] > )

                     {

                         maps[][q.x][q.y] = q.t;

                         maps[][q.x][q.y] = ;

                         q.dir = ;

                         Q.push (q);

                     }

                 }

         }

     }

 }

 int main ()

 {

     int n, s;

     while (scanf ("%d %d %d %d", &r, &c, &n, &t) != EOF)

     {

         memset (maps, , sizeof(maps));

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

         {

             scanf ("%d %d %d", &x, &y, &s);

             point[i][] = x;

             point[i][] = y;

             maps[][x][y] = s;

         }

         scanf ("%d %d", &x, &y);

         bfs ();

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

         {

             x = point[i][];

             y = point[i][];

             if (maps[][x][y] == )

                 printf ("0 %d\n", maps[][x][y]);

             else

                 printf ("1 %d\n", maps[][x][y]);

         }

     }

     return ;

 }

巴特西

Hdu 5336 XYZ and Drops (bfs 模拟)

最新文章

热门文章