注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4527 小明系列故事——玩转十滴水  

2014-03-27 00:13:04|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4527
搜索模拟
刚开始是这么做的:用优先队列维护,加上一滴水后看是否会爆炸,如果会爆炸则进队列,然后四个方向找小水滴的融合处,如果还有会爆炸的进入队列,过程中记录每个点爆炸的时间,如果经过的点当前时刻已经爆炸则继续寻找,否则把该点进队列。这样处理,有个bug,有可能时刻靠后的先被进队列。
例如4 4 0 4 4 2,第二个位置放一滴,第5个位置就会有两个时刻的水滴到达,时刻靠后的水滴会被抹掉。如果改过来,又会和样例1起矛盾。所以这个想法有漏洞,不可取。

后来换了一种想法:按照时间来模拟小水滴,用两个队列维护。如果初始水滴要爆炸,则把四个方向的水滴进入队列1,队列1里的水滴如果遇到0则往前再走一步并且进入队列2,否则当前位置+1;遍历一遍矩阵,如果有水滴要爆炸,则四个方向的水滴进入队列2,然后同理执行队列2,两个队列换着用。
*bfs还是得按照过程一步步模拟,才能避免出错。

struct Node{
int tx,ty,dir;
};
queue<Node>Q[2];
int f[8][8];
int vis[8][8];

int jud(Node p)
{
if(p.tx<1 || p.tx>6 || p.ty<1 || p.ty>6)
return 0;
return 1;
}

void bfs(int x,int y)
{
if(f[x][y] < 4)
{
f[x][y]++;
return ;
}
f[x][y]=0;
Node p,q;
int sig=0;
while(!Q[0].empty())
Q[0].pop();
while(!Q[1].empty())
Q[1].pop();
for(int i=0;i<4;i++)
{
p.tx=x+dir4[i][0];
p.ty=y+dir4[i][1];
p.dir=i;
Q[sig].push(p);
}
while(1)
{
while(!Q[sig].empty())
{
p=Q[sig].front();
Q[sig].pop();
if(!jud(p))
continue;
if(f[p.tx][p.ty] == 0)
{
q.tx=p.tx+dir4[p.dir][0];
q.ty=p.ty+dir4[p.dir][1];
q.dir=p.dir;
if(jud(q))
Q[1-sig].push(q);
}
else
f[p.tx][p.ty]++;
}
for(int i=1;i<=6;i++)
for(int j=1;j<=6;j++)
if(f[i][j] > 4)
{
f[i][j]=0;
for(int t=0;t<4;t++)
{
p.tx=i+dir4[t][0];
p.ty=j+dir4[t][1];
p.dir=t;
Q[1-sig].push(p);
}
}
if(Q[1-sig].empty())
return ;
sig=1-sig;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int m,a,b;
while(scanf("%d",&f[1][1])!=EOF)
{
for(int i=2;i<=6;i++)
sf(f[1][i]);
for(int i=2;i<=6;i++)
for(int j=1;j<=6;j++)
sf(f[i][j]);
sf(m);
while(m--)
{
sf2(a,b);
bfs(a,b);
}
for(int i=1;i<=6;i++)
{
for(int j=1;j<=6;j++)
{
if(j > 1)
printf(" ");
printf("%d",f[i][j]);
}
pfn;
}
pfn;
}
return 0;
}

  评论这张
 
阅读(64)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017