?pid=5336
Problem Description
XYZ is playing an interesting game called "drops". It is played on agrid. Each grid cell is either empty, or occupied by a waterdrop. Each waterdrop has a property "size". The waterdrop cracks when its size is larger than 4, and produces 4 small drops moving towards 4 different directions (up, down, left and right).In every second, every small drop moves to the next cell of its direction. It is possible that multiple small drops can be at same cell, and they won’t collide. Then for each cell occupied by a waterdrop, the waterdrop’s size increases by the number of the small drops in this cell, and these small drops disappears.You are given a game and a position (), before the first second there is a waterdrop cracking at position (). XYZ wants to know each waterdrop’s status afterseconds, can you help him?
Input
The first line contains four integersstands for the numbers of waterdrops at the beginning.Each line of the followinglines contains three integers, meaning that the-th waterdrop is at position () and its size is. ()The next line contains two integers.It is guaranteed that all the positions in the input are distinct.Multiple test cases (about 100 cases), please read until EOF (End Of File).
Output
lines. Each line contains two integers:If the-th waterdrop cracks inthe time when it cracked.If the-th waterdrop doesn’t crack inits size afterseconds.
Sample Input
4 4 5 102 1 42 3 32 4 43 1 24 3 44 4
Sample Output
0 50 30 21 30 1
/**hdu5336 多校联合第四场1010 模拟+bfs题目大意：很像一个游戏“十滴水”，在一个n*m的棋盘里有N个点有一些水滴，含水量为1~4,如果一滴水多于4则该水滴会向四个方向放射量为1的水，并且原位置水滴消逝，放射的水运动速度为1格/s，最开始在xy位置有一滴水崩裂，问T s时各初始状态的水滴的状态是什么解题思路：因为水滴的迸射会产生连锁反应，，因此我们用优先队列维护，bfs。值得一提的是如果2或以上的水同时到达一水滴，并该水滴迸射那么这些水滴同时消失。*/#include <string.h>#include <algorithm>#include <iostream>#include <stdio.h>#include <queue>using namespace std;int n,m,N,T,num[1005][2],sta[1005][1005],time[1005][1005];int dx[][2]= {1,0,0,1,-1,0,0,-1};struct note{int x,y,d,t;note() {}note(int _x,int _y,int _d,int _t){x=_x,y=_y,d=_d,t=_t;}bool operator < (const note &other)const{return t>other.t;}};void bfs(int x,int y){memset(time,-1,sizeof(time));priority_queue<note> q;q.push(note(x,y,0,0));q.push(note(x,y,1,0));q.push(note(x,y,2,0));q.push(note(x,y,3,0));while(!q.empty()){note cnt=q.top();if(cnt.t>=T)return;q.pop();x=cnt.x+dx[cnt.d][0];y=cnt.y+dx[cnt.d][1];if(x<=0||x>n||y<=0||y>m||time[x][y]==cnt.t+1)continue;if(sta[x][y]!=0){if(sta[x][y]==4){sta[x][y]=0;time[x][y]=cnt.t+1;q.push(note(x,y,0,cnt.t+1));q.push(note(x,y,1,cnt.t+1));q.push(note(x,y,2,cnt.t+1));q.push(note(x,y,3,cnt.t+1));}else{sta[x][y]++;}}elseq.push(note(x,y,cnt.d,cnt.t+1));}}int main(){while(~scanf("%d%d%d%d",&n,&m,&N,&T)){memset(sta,0,sizeof(sta));for(int i=0; i<N; i++){int x;scanf("%d%d%d",&num[i][0],&num[i][1],&x);sta[num[i][0]][num[i][1]]=x;}int x,y;scanf("%d%d",&x,&y);bfs(x,y);for(int i=0; i<N; i++){if(time[num[i][0]][num[i][1]]==-1)printf("1 %d\n",sta[num[i][0]][num[i][1]]);elseprintf("0 %d\n",time[num[i][0]][num[i][1]]);}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
不论你在什么时候结束，重要的是结束之后就不要悔恨
