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

推荐阅读

boost|性能太激进！一加10 Pro发布，不俗产品力拉开竞品差距

实用软件|Mathematica，亮瞎你的双眼

感染气性坏疽怎么办？

安卓图标下载,安卓手机桌面图标消失如何恢复?

食物鸳鸯配营养能翻倍

sata固态比nvme贵怎么4k对齐

尸斑是怎么形成的尸斑什么时候出现的

bf地面站osd中文菜单，OSD菜单在哪如何给显示器消磁

做作业用英语怎么说作业的英语说法是什么

房产来源怎么填

如何养好紫蝴蝶三叶草紫蝴蝶三叶草可以水培么

竹节参治什么病竹节参常见病虫害及防治

向银行申请贷款必须提供担保吗？

每年三伏天一共多少天

面积最小的是印度洋还是北冰洋面积最小的是印度洋还是北冰洋

涂抹粉底前需要先用哪些护肤品粉底在哪个步骤用

手机播放U盘可以吗

关于春节的祝福语

高铁厕所可以上大便吗

公主连结9月6日更新内容预告公主连接六星解锁nnk卡池