HDU 5336(2015多校4)-XYZ and Drops(bfs)
分类：HDU ojBFS
题目地址：HDU 5336 题意：有一个r 行 c 列的格子，给出n个格子里有水滴的大小。再给出时间限制T，使得水滴从(sx,sy)位置开始爆破，当飞渐的水遇到格子里的静态水时就会聚在一起，当聚集的水滴大小>4时就会爆破。问在T时给定的n个位置格子里的水滴情况，，如果没有爆破就输出：1 格子里水滴大小。否则输出：0 爆破的时间。
;LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;int mp[110][110];int time[110][110];int jx[]= {0,1,0,-1};int jy[]= {1,0,-1,0};int r,c,n,T;int sx,sy;struct drop {int x,y;int time;int papa;} f1,f2;void bfs(int xx,int yy){queue<drop>q;f1.x=xx;f1.y=yy ;f1.time=0;f1.papa=-1;q.push(f1);while(!q.empty()){f1=q.front();q.pop();if(f1.papa>=0){f2.x=f1.x+jx[f1.papa];f2.y=f1.y+jy[f1.papa];f2.time=f1.time+1;if(f2.x>=1&&f2.x<=r&&f2.y>=1&&f2.y<=c&&f2.time<=T){if(mp[f2.x][f2.y]){mp[f2.x][f2.y]++;if(mp[f2.x][f2.y]==5){f2.papa=-1;q.push(f2);}}else{f2.papa=f1.papa;q.push(f2);}}}else{time[f1.x][f1.y]=f1.time;mp[f1.x][f1.y]=0;for(int i=0; i<4; i++){f2.x=f1.x+jx[i];f2.y=f1.y+jy[i];f2.time=f1.time+1;if(f2.x>=1&&f2.x<=r&&f2.y>=1&&f2.y<=c&&f2.time<=T){if(mp[f2.x][f2.y]){mp[f2.x][f2.y]++;if(mp[f2.x][f2.y]==5){f2.papa=-1;q.push(f2);}}else{f2.papa=i;q.push(f2);}}}}}}int main(){int v;drop node[110];while(~scanf(“%d %d %d %d”,&r,&c,&n,&T)){memset(mp,0,sizeof(mp));for(int i=0;i<n;i++){scanf(“%d %d %d”,&sx,&sy,&v);node[i].x=sx;node[i].y=sy;mp[sx][sy]+=v;}scanf(“%d %d”,&sx,&sy);bfs(sx,sy);for(int i=0;i<n;i++)if(mp[node[i].x][node[i].y])printf(“1 %d\n”,mp[node[i].x][node[i].y]);elseprintf(“0 %d\n”,time[node[i].x][node[i].y]);}}/*同一时间到达同一个水滴(所以代码里是==5而不是>4)4 4 5 1001 1 41 2 31 3 41 4 42 3 42 41 41 40 20 10 1*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇HDU 5328(2015多校4)-Problem Killer(水题)下一篇HDU 5339-Untitled(枚举)
顶1踩0
旅行还在继续，这个过程是艰难而又孤单的。
