POJ3414 图 - 锐客网

POJ3414pots 【POJ3414】这些bfs题都很妙啊，多做做肯定有好处的
思路:
每到一次可以作为一个方向，总共有6种方向
①把A装满
②把B装满
③把A倒了
④把B倒了
⑤把A倒入B
⑥把B倒入A
其实就是bfs，每次操作先看看是否到达过，然后标记，然后顺着找。总共三个数（100以内），能有多少种组合？
直接用二维数组就可以

#include #include #include #include #include #include #include #include #include #include #include using namespace std; int a,b,c; int vis [105][105]; struct node { int u,v; int level; int caozuo; int id; int pre; node(int a,int a1,int a2,int a3,int a4,int a5) { u=a; v=a1; level=a2; caozuo=a3; id=a4; pre=a5; } }; vector arr; int cnt=0; int ans; string str[]= { "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)" }; void bfs() { queue cun; cun.push(node(0,0,0,-1,0,-1)); arr.push_back(node(0,0,0,-1,0,-1)); memset(vis,0,sizeof(vis)); vis[0][0]=1; cnt++; ans=-1; while(!cun.empty()) { node tmp=cun.front(); cun.pop(); if(tmp.u==c||tmp.v==c) { ans=tmp.id; break; }for(int i=0; i<6; i++) { if(i==0)//fill a { if(a-tmp.u>0&&vis[a][tmp.v]==0) { vis[a][tmp.v]=1; node n(a,tmp.v,tmp.level+1,i,cnt,tmp.id); cnt++; arr.push_back(n); cun.push(n); } } else if(i==1) //fill b { if(b-tmp.v>0&&vis[tmp.u][b]==0) { vis[tmp.u][b]=1; node n(tmp.u,b,tmp.level+1,i,cnt,tmp.id); cnt++; arr.push_back(n); cun.push(n); } } else if(i==2) //d a { if(tmp.u>0&&vis[0][tmp.v]==0) { vis[0][tmp.v]=1; node n(0,tmp.v,tmp.level+1,i,cnt,tmp.id); cnt++; arr.push_back(n); cun.push(n); } } else if(i==3) //d b { if(tmp.v>0&&vis[tmp.u][0]==0) { vis[tmp.u][0]=1; node n(tmp.u,0,tmp.level+1,i,cnt,tmp.id); cnt++; arr.push_back(n); cun.push(n); } } else if(i==4) //1->2 { if(tmp.u!=0&&tmp.v!=b) { int dao=min(b-tmp.v,tmp.u); if(vis[tmp.u-dao][tmp.v+dao]==0) { vis[tmp.u-dao][tmp.v+dao]=1; node n(tmp.u-dao,tmp.v+dao,tmp.level+1,i,cnt,tmp.id); cnt++; arr.push_back(n); cun.push(n); }} } else if(i==5) { if(tmp.v!=0&&tmp.u!=a) { int dao=min(a-tmp.u,tmp.v); if(vis[tmp.u+dao][tmp.v-dao]==0) { vis[tmp.u+dao][tmp.v-dao]=1; node n(tmp.u+dao,tmp.v-dao,tmp.level+1,i,cnt,tmp.id); cnt++; arr.push_back(n); cun.push(n); }} }} }if(ans!=-1) { node tmp=arr[ans]; int cnt=0; stack arrx; while(1) { if(tmp.caozuo>=6||tmp.caozuo<0) break; arrx.push(tmp.caozuo); ans=tmp.pre; if(ans==-1) break; tmp=arr[tmp.pre]; cnt++; } cout<>a>>b>>c; bfs(); return 0; }

POJ3414

推荐阅读

人民币1元硬币背面什么花人民币硬币1角是什么花

安德烈娅·盖兹|安德烈娅·盖兹银河系中心的芭蕾舞者

西门子冰箱工作时声音大正常吗常见故障,以及处理方式？

安县美食安县美食都有哪些

笔记本屏幕发黄修复小技巧笔记本屏幕发黄修复小技巧有哪些

绿色底纹怎么设置

苦参内服的功效与作用苦参内服有哪些功效作用

移动html5动画效果，html5做动画

安卓qq卡住怎么办,手机出现办卡空间不足问题四大注意事项

背影的作者是谁作者简介背影的作者是哪个作者简介

等价无穷小的错误用法等价无穷小的适用范围

2018/12/28|2018/12/28 胡萝卜鸡蛋煎饼

如何用心理学解释星座学是伪科学？

mini|欧亚监管文件曝光新款 Mac/Apple Watch

可以用电视机做电脑显示器吗电视和显示器有什么区别

幼儿园设计|幼儿园设计|地面空间不够（那试试在屋顶开辟活动空间吧）

电脑在哪里设置开机密码

移动服务器传奇私服，手机传奇服务端下载

编程软件的图标，编程的图标是哪个啊

地薄者大物不产