ACM搜索 POJ 3414 BFS解题报告

《ACM搜索 POJ 3414 BFS解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*题目要求：两个桶的体积分别为A和B，要求用这个两个桶装出C体积的水，如果可以的话就输出装法，不可以的话就输出impossibie. A，B<=100，并且是要求输出最少的步数和方法。SampleInput354SampleOutput6FILL(2)POUR(2,1)DROP(1)POUR(2,1)FILL(2)POUR(2,1)简单运用BFS的典型例题*/#include#include#includeusingnamespacestd;classNode{public:inta;intb;str

2、ingfunction;//保存路径六种选择用六个数字表示Node(){};Node(inta,intb,stringfunction){this->a=a;this->b=b;this->function=function;}};intmain(){queueq;inta,b,c;cin>>a>>b>>c;Nodestart(0,0,"");Nodefinal;//最终节点boolflag[101][101];//通过ab判断是否出现过此状态memset(flag,true,sizeof(flag));//如果用boolflag[101]

3、[101]=true;下面修改数组元素值会发生错误booljudge=false;q.push(start);while(!q.empty())//BFS{start=q.front();q.pop();for(inti=0;i<6;i++){switch(i){case0:{Nodetemp(0,start.b,start.function+'0');if(temp.a==c

4、

5、temp.b==c){judge=true;final=temp;}if(flag[temp.a][temp.b]==true){flag[temp.a][temp.b]=f

6、alse;q.push(temp);}break;}case1:{Nodetemp(start.a,0,start.function+'1');if(temp.a==c

7、

8、temp.b==c){judge=true;final=temp;}if(flag[temp.a][temp.b]==true){flag[temp.a][temp.b]=false;q.push(temp);}break;}case2:{Nodetemp(a,start.b,start.function+'2');if(temp.a==c

9、

10、temp.b==c){judge=tru

11、e;final=temp;}if(flag[temp.a][temp.b]==true){flag[temp.a][temp.b]=false;q.push(temp);}break;}case3:{Nodetemp(start.a,b,start.function+'3');if(temp.a==c

12、

13、temp.b==c){judge=true;final=temp;}if(flag[temp.a][temp.b]==true){flag[temp.a][temp.b]=false;q.push(temp);}break;}case4:{if(sta

14、rt.a>b-start.b){Nodetemp(start.a-(b-start.b),b,start.function+'4');if(temp.a==c

15、

16、temp.b==c){judge=true;final=temp;}if(flag[temp.a][temp.b]==true){flag[temp.a][temp.b]=false;q.push(temp);}}else{Nodetemp(0,start.a+start.b,start.function+'4');if(temp.a==c

17、

18、temp.b==c){judge=true;fin

19、al=temp;}if(flag[temp.a][temp.b]==true){flag[temp.a][temp.b]=false;q.push(temp);}}break;}case5:{if(start.b>a-start.a){Nodetemp(a,b-(a-start.a),start.function+'5');if(temp.a==c

20、

21、temp.b==c){judge=true;final=temp;}if(flag[temp.a][temp.b]==true){flag[temp.a][temp.b]=false;q.push(tem

22、p);}}else{Nodetemp(start.a+start.b,0,start.func