hdu 4527 小明系列故事之玩转十滴水

hdu 4527 小明系列故事之玩转十滴水2014-03-17 csdn博客 shuangde800小明最近喜欢上了一个名为十滴水的游戏。

游戏是在一个6*6的方格内进行的，每个格子上有一滴水或者没有水滴。水滴分为四个等级1~4。初始时你有十滴水，通过把水加入格子内的水滴，会让水滴升1级。你也可以把水放到空格子内，这样会在这个格子里面产生一个1级的水滴。当水滴等级大于4时则会爆裂为四个小水滴，并向四个方向飞溅。每个飞溅的小水滴碰到其他水滴后会融入其中，使其升一级或者爆裂，以此类推。飞溅的小水滴互不干扰，运动速度相等（1秒可以移动一个格子的距离）。水滴爆裂后就消失掉了。

思路：

直接用bfs来模拟，注意模拟时要一个单位时间一个单位时间的走，如果两个水滴同时到达另一个水滴，那么那个水滴+2。

这秒走完以后，再看把所有点中大于4的要爆炸的水滴处理成四个方向上的水滴并入队列，然后继续走下一秒。

#include<cstdio>#include<cmath>#include<cstring>#include<iostream>#include<algorithm>using namespace std; typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 10010; int m;int mat[8][8];int blast[8][8];// 上，下，左，右const int dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}}; struct Node{int x, y;int cnt;int dir;}Q[500000]; void addQue（int x, int y, int cnt, int& rear）{mat[x][y] = 0;for（int i=0; i<4; ++i）{int dx = x + dir[i][0];int dy = y + dir[i][1];if（dx>=1&&dx<=6&&dy>=1&&dy<=6）{Q[rear].x = dx;Q[rear].y = dy;Q[rear].cnt = cnt;Q[rear++].dir = i;}}} void bfs（int x, int y）{int front=0, rear=0; addQue（x, y, 0, rear）; int cur = 0; //当前第几秒 while（front < rear）{ while（front < rear && Q[front].cnt==cur）{ //把这一秒的全走完 Node &t = Q[front++];if（mat[t.x][t.y]）{++mat[t.x][t.y];} else{Node& now = Q[rear];now.x = t.x + dir[t.dir][0];now.y = t.y + dir[t.dir][1];now.cnt = t.cnt + 1;now.dir = t.dir;if（now.x>=1&&now.x<=6&&now.y>=1&&now.y<=6）++rear;}}for（int i=1; i<=6; ++i）{for（int j=1; j<=6; ++j）if（mat[i][j]>4）{addQue（i,j,cur+1,rear）;}}++cur;}}int main（）{ int x, y;while（~scanf（"%d", &mat[1][1]））{ for（int i=1; i<=6; ++i）{for（int j=（i==1？2:1）; j<=6; ++j）{scanf（"%d", &mat[i][j]）;}}scanf（"%d", &m）;for（int i=0; i<m; ++i）{scanf（"%d%d", &x, &y）;if（++mat[x][y]>4）{bfs（x, y）;}} for（int i=1; i<=6; ++i）{for（int j=1; j<=6; ++j）if（j！=1） printf（" %d", mat[i][j]）;else printf（"%d", mat[i][j]）;putchar（"
"）;}putchar（"
"）; }return 0;}