小明系列故事——玩转十滴水
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 728 Accepted Submission(s): 287
http://acm.split.hdu.edu.cn/showproblem.php?pid=4527
Problem Description
小明最近喜欢上了一个名为十滴水的游戏。
游戏是在一个6*6的方格内进行的，每个格子上有一滴水或者没有水滴。水滴分为四个等级1~4。初始时你有十滴水，通过把水加入格子内的水滴，会让水滴升1级。你也可以把水放到空格子内，这样会在这个格子里面产生一个1级的水滴。当水滴等级大于4时则会爆裂为四个小水滴，并向四个方向飞溅。每个飞溅的小水滴碰到其他水滴后会融入其中，使其升一级或者爆裂，以此类推。飞溅的小水滴互不干扰，运动速度相等(1秒可以移动一个格子的距离)。水滴爆裂后就消失掉了。
游戏是在一个6*6的方格内进行的，每个格子上有一滴水或者没有水滴。水滴分为四个等级1~4。初始时你有十滴水，通过把水加入格子内的水滴，会让水滴升1级。你也可以把水放到空格子内，这样会在这个格子里面产生一个1级的水滴。当水滴等级大于4时则会爆裂为四个小水滴，并向四个方向飞溅。每个飞溅的小水滴碰到其他水滴后会融入其中，使其升一级或者爆裂，以此类推。飞溅的小水滴互不干扰，运动速度相等(1秒可以移动一个格子的距离)。水滴爆裂后就消失掉了。
Input
题目包含多组测试用例；
对于每组数据，首先是6行，每行有6个整数数字，每个数字的范围为0~4；当数字为0时，表示空格子，当数字为1~4时，表示1~4级的水滴；
然后第七行是一个整数m，表示有m个操作；接下来是m行，每行有两个整数x, y ，表示在(x,y)放入一滴水。
特别说明：每次都是在全部的水滴静止后才进行下一次操作，也就是说只有在方格内没有任何飞溅的小水滴时才能放入一滴水。
[Technical Specification]
1 <= m <= 10
1 <= x, y <= 6
对于每组数据，首先是6行，每行有6个整数数字，每个数字的范围为0~4；当数字为0时，表示空格子，当数字为1~4时，表示1~4级的水滴；
然后第七行是一个整数m，表示有m个操作；接下来是m行，每行有两个整数x, y ，表示在(x,y)放入一滴水。
特别说明：每次都是在全部的水滴静止后才进行下一次操作，也就是说只有在方格内没有任何飞溅的小水滴时才能放入一滴水。
[Technical Specification]
1 <= m <= 10
1 <= x, y <= 6
Output
对于每组测试数据，请输出m个操作之后6*6方格内水滴的样子，每组数据的输出后面跟着一个空行。
很棒的模拟题~~每次滴完水后判断滴的格子水滴等级是否大于4，小于4继续下一个滴水操作，大于4就开始模拟小水滴飞溅的过程。
小水滴是有速度的（1秒1个格子）所以我们模拟时要针对每一秒进行，考虑方格中一秒内能发生的事件：
1.飞溅的小水滴向前移动一格
2.飞溅的小水滴飞出地图
2.飞溅的小水滴与前方水滴融合，前方水滴等级+1
3.水滴等级大于4，爆裂，分出朝四个方向飞溅的小水滴。
我们使用一个队列，保存所有这一秒方格上存在的小水滴的位置，使用另一个队列，保存所有小水滴下一秒到达的位置。
每秒一轮操作，直到两个队列都为空~就表示所有飞溅的小水滴都被处理掉啦~
被这题的输出坑了好多次，以为只要格子里的一旦没有飞溅的小水滴时就输出一次，还是要认真看好题目要求啊！
#include <iostream> #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; int f[4][2]={0,1,-1,0,0,-1,1,0},flag; int mp[10][10]; struct node { int x,y,f; }; queue<node>q,qq;//两个队列分别存这一秒飞溅的水滴以及下一秒的 node s,t; void init() { for(int i=1;i<=6;i++) for(int j=1;j<=6;j++) { if(i==1&&j==1)continue; scanf("%d",&mp[i][j]); } } bool jug(int x,int y) { if(x<1||x>6||y<1||y>6)return false; return true; } void get_di(int x,int y) { mp[x][y]=0; for(int i=0;i<4;i++) { s.x=x+f[i][0],s.y=y+f[i][1],s.f=i; if(jug(s.x,s.y)) { qq.push(s); } } } void print() { for(int i=1;i<=6;i++) { for(int j=1;j<=6;j++) { if(j==1)printf("%d",mp[i][j]); else printf(" %d",mp[i][j]); } printf(" "); } } void scanner(int x,int y) { while(!q.empty())q.pop(); while(!qq.empty())qq.pop(); if(mp[x][y]<4){mp[x][y]++;return;} mp[x][y]=0; for(int i=0;i<4;i++) { s.x=x+f[i][0],s.y=y+f[i][1],s.f=i; if(jug(s.x,s.y)) q.push(s); } while(1) //模拟每一秒的状态 { flag=0; while(!q.empty()) { flag=1; s=q.front();q.pop(); if(mp[s.x][s.y]==0) { t.x=s.x+f[s.f][0],t.y=s.y+f[s.f][1],t.f=s.f; if(jug(t.x,t.y)) qq.push(t); } if(mp[s.x][s.y]>0)mp[s.x][s.y]++; } for(int i=1;i<=6;i++) for(int j=1;j<=6;j++) if(mp[i][j]>4)flag=1,get_di(i,j); swap(q,qq); if(!flag)break; } } int main() { int m,x,y; while(~scanf("%d",&mp[1][1])){ init(); scanf("%d",&m); while(m--){ scanf("%d %d",&x,&y); scanner(x,y); } print(); printf(" "); } return 0; }