首页 > 代码库 > HDU 5012 BFS水
HDU 5012 BFS水
2014 ACM/ICPC Asia Regional Xi‘an Online
对于一个筛子,规定了以底面的四个边为轴,可以进行翻转,给出起始状态,求最少步骤到目标状态。
简单BFS
#include "stdio.h" #include "string.h" #include "math.h" #include "queue" using namespace std; struct node { int s[7]; int status,step; }; int aim,a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,b5,b6,ans; int hash[1001000]; int dfs() { queue<node>q; node cur,next; int i; cur.s[1]=a1; cur.s[2]=a2; cur.s[3]=a3; cur.s[4]=a4; cur.s[5]=a5; cur.s[6]=a6; cur.status=0; for (i=1;i<=6;i++) cur.status=cur.status*10+cur.s[i]; hash[cur.status]=1; cur.step=0; q.push(cur); while (!q.empty()) { cur=q.front(); q.pop(); next.s[1]=cur.s[6]; next.s[2]=cur.s[5]; next.s[3]=cur.s[3]; next.s[4]=cur.s[4]; next.s[5]=cur.s[1]; next.s[6]=cur.s[2]; next.status=0; for (i=1;i<=6;i++) next.status=next.status*10+next.s[i]; if (hash[next.status]==0) { hash[next.status]=1; next.step=cur.step+1; q.push(next); if (next.status==aim) return next.step;} next.s[1]=cur.s[5]; next.s[2]=cur.s[6]; next.s[3]=cur.s[3]; next.s[4]=cur.s[4]; next.s[5]=cur.s[2]; next.s[6]=cur.s[1]; next.status=0; for (i=1;i<=6;i++) next.status=next.status*10+next.s[i]; if (hash[next.status]==0) { hash[next.status]=1; next.step=cur.step+1; q.push(next);if (next.status==aim) return next.step;} next.s[1]=cur.s[4]; next.s[2]=cur.s[3]; next.s[3]=cur.s[1]; next.s[4]=cur.s[2]; next.s[5]=cur.s[5]; next.s[6]=cur.s[6]; next.status=0; for (i=1;i<=6;i++) next.status=next.status*10+next.s[i]; if (hash[next.status]==0) { hash[next.status]=1; next.step=cur.step+1; q.push(next);if (next.status==aim) return next.step;} next.s[1]=cur.s[3]; next.s[2]=cur.s[4]; next.s[3]=cur.s[2]; next.s[4]=cur.s[1]; next.s[5]=cur.s[5]; next.s[6]=cur.s[6]; next.status=0; for (i=1;i<=6;i++) next.status=next.status*10+next.s[i]; if (hash[next.status]==0) { hash[next.status]=1; next.step=cur.step+1; q.push(next);if (next.status==aim) return next.step;} } return -1; } int main() { while (scanf("%d%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5,&a6)!=EOF) { scanf("%d%d%d%d%d%d",&b1,&b2,&b3,&b4,&b5,&b6); if (a1==b1 && a2==b2 && a3==b3 && a4==b4 && a5==b5 && a6==b6) { printf("0\n"); continue; } aim=b1*100000+b2*10000+b3*1000+b4*100+b5*10+b6; ans=-1; memset(hash,0,sizeof(hash)); ans=dfs(); printf("%d\n",ans); } return 0; }
HDU 5012 BFS水
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。