HDU 5336 BFS+模拟

分类：搜索

模拟十滴水游戏

r*c矩阵中，，共有N个大水滴，求T秒后这N个水滴的状态

在0秒时在s_x,s_y位置有个水滴爆炸，生成向四周移动的小水滴，每个大水滴>4会爆炸，生成向四周移动的小水滴

把所有小水滴入队列，进行BFS即可，注意处理多个小水滴同时到达同一个大水滴的情况

#include "stdio.h"#include "string.h"#include "queue"using namespace std;const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };struct node{int x,y,dir;};struct Mark{int x,y,cra;}mark[110];int r,c,n,t,s_x,s_y;int mp[110][110],id[110][110];void init(){int i,x,y,z;memset(mp,0,sizeof(mp));memset(id,0,sizeof(id));for (i=1;i<=n;i++){scanf("%d%d%d",&x,&y,&z);mp[x][y]+=z;id[x][y]=i;mark[i].x=x;mark[i].y=y;mark[i].cra=0;}scanf("%d%d",&s_x,&s_y);}void bfs(){queue<node>q1,q2;node cur;int i,j,cnt,time;cur.x=s_x; cur.y=s_y;for (i=0;i<4;i++){cur.dir=i;q1.push(cur);}time=0;cnt=0;while (time<t){time++;while (!q1.empty()){cur=q1.front();q1.pop();cur.x+=dir[cur.dir][0];cur.y+=dir[cur.dir][1];if (cur.x<1 || cur.y<1 || cur.x>r || cur.y>c) continue;mp[cur.x][cur.y]++;if (id[cur.x][cur.y]==0)q2.push(cur);}for (i=1;i<=n;i++) // 检查是否有新的大水滴爆炸if (mark[i].cra==0){if (mp[mark[i].x][mark[i].y]>4){mp[mark[i].x][mark[i].y]=0;id[mark[i].x][mark[i].y]=0;mark[i].cra=time;cnt++;cur.x=mark[i].x; cur.y=mark[i].y;for (j=0;j<4;j++)// 生成新的4个小水滴{cur.dir=j;q1.push(cur);}}}if (cnt==n) break;while (!q2.empty()) //将没有使大水滴爆炸的小水滴继续进队列{cur=q2.front();q2.pop();if (mp[cur.x][cur.y]==0) continue;q1.push(cur);}}}void pri(){int i;for (i=1;i<=n;i++)if (mark[i].cra!=0)printf("0 %d\n",mark[i].cra);elseprintf("1 %d\n",mp[mark[i].x][mark[i].y]);}int main(){while (scanf("%d%d%d%d",&r,&c,&n,&t)!=EOF){init();bfs();pri();}return 0;}

上一篇HDU 5316 线段树区间最值问题下一篇HDU 5335 贪心+BFS

顶0踩0

上天完全是为了坚强你的意志，才在道路上设下重重的障碍。

相关文章：

你感兴趣的文章：

标签云：