【HDOJ 5336】XYZ and Drops

分类：HDOJDFS&BFS

bfs

挺坑爹的一题……十滴水小游戏的游戏规则可以去玩玩看…… 主要有三种状态爆炸、扩散和融合

水滴爆炸形成四滴水指向上下左右四个方向下一秒流向四周小水滴(流动中的水) 碰到大水滴大水滴立即爆炸 (若同时多个方向水滴汇集到一个大水滴(融合) 全部融入后大水滴才爆炸)

各种姿势各种判定加啊…………后来发现正确姿势是把该秒大水滴遍历完遍历小水滴由秒数和队列是否空来判断跳出

代码如下(略乱):

;typedef struct Point{int x,y,step,dir;bool r;}Point;Point pt[111];int r,c,n,t;int id[111][111],sd[111][111];int dirx[] = { 0, 0, 1,-1};int diry[] = { 1,-1, 0, 0};bool bz[111][111],vis[111][111];void bfs(int sx,int sy){Point p;memset(vis,0,sizeof(vis));queue <Point> q;queue <Point> ss;q.push(Point{sx,sy,0,0,0});int i,x,y;while(!q.empty() || !ss.empty()){if(q.empty() ||(!ss.empty() && q.front().step > ss.front().step)){p = ss.front();ss.pop();if(p.step == t) return;}else{p = q.front();q.pop();vis[p.x][p.y] = 0;}if(p.step > t) return;//printf(“x%d y%d st%d %s\n”,p.x,p.y,p.step,p.r? “run”: “sd”);if(p.r){x = p.x + dirx[p.dir];y = p.y + diry[p.dir];if(x <= 0 || x > r || y <= 0 || y > c) continue;if(bz[x][y]){//printf(“%d %d->%d %d %d s流动\n”,p.x,p.y,x,y,p.step+1);ss.push(Point{x,y,p.step+1,p.dir,1});}else{//printf(“%d %d->%d %d %d s融合\n”,p.x,p.y,x,y,p.step+1);sd[x][y]++;if(!vis[x][y]){q.push(Point{x,y,p.step+1,0,0});vis[x][y] = 1;}}continue;}if(p.x == sx && p.y == sy ||(!bz[p.x][p.y] && sd[p.x][p.y] > 4)){bz[p.x][p.y] = 1;pt[id[p.x][p.y]].step = p.step;//printf(“%d %d %d滴水 %d爆炸\n”,p.x,p.y,sd[p.x][p.y],p.step);for(i = 0; i < 4; ++i){x = p.x + dirx[i];y = p.y + diry[i];if(x <= 0 || x > r || y <= 0 || y > c) continue;if(!bz[x][y]){if(p.step < t)sd[x][y]++;if(!vis[x][y]){q.push(Point{x,y,p.step+1,0,0});vis[x][y] = 1;}}else ss.push(Point{x,y,p.step+1,i,1});}}}}int main(){int i,x,y;while(~scanf(“%d %d %d %d”,&r,&c,&n,&t)){memset(bz,1,sizeof(bz));memset(sd,0,sizeof(sd));for(i = 0; i < n; ++i){scanf(“%d %d”,&x,&y);scanf(“%d”,&sd[x][y]);pt[i].x = x;pt[i].y = y;id[x][y] = i;bz[x][y] = 0;}scanf(“%d%d”,&x,&y);bfs(x,y);for(i = 0; i < n; ++i){x = pt[i].x;y = pt[i].y;if(!bz[x][y]) printf(“1 %d\n”,sd[x][y]);else printf(“0 %d\n”,pt[i].step);}}return 0;}

上一篇【HDOJ 5328】 Problem Killer下一篇【HDOJ 1010】Tempter of the Bone

顶0踩0

，鱼儿爱美，不仅需要鳞甲之美。还需要浮沉活泼之美。

相关文章：

你感兴趣的文章：

标签云：