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

推荐阅读

redis多用户登录 redis多账号密码

和田玉手牌_真玉和假玉在灯光下有啥区别

用颜料画的画大全如何用水彩画蛋，水彩画用什么笔勾线

使用|使用 SAP HANA Virtual Table 连接外部数据源

redis连接失败什么意思 redis无法连接rst

吃草莓会拉红色大便吗

期货如何设置止损

iQOO|iQOO Z5开售了！价格便宜又配备了5000mAh容量电池

上海大学分数线上海大学高考分数线

猫咪身上有凸起的包会动

鸿蒙系统nova5ipro升级时间介绍

三星GalaxyView平板电脑风扇坏了怎么修理

9点45分怎么弄时钟图片,一个钟表疯狂猜成语答案大全图片

y53sT2版和标准版的区别

ross|消息称苹果iPhone 14 Pro采用“感叹号”打孔，无缘屏下Face ID

如何制作马克思发生器视频

T区抗氧化需要什么护肤品

奔图P2550打印机老卡纸维修报价

华为m买手机就应该选用得久的，目前这4部手机最值得买，好看又好用

威能半冷凝壁挂炉代码如何解决