首页 > 代码库 > BFS/poj 3414 pots
BFS/poj 3414 pots
#include<cstdio>#include<queue>#include<cstring>using namespace std;struct point{ int a,b; int step; int way[110];};int aa,bb,cc;int v[110][110];void bfs(){ memset(v,0,sizeof(v)); queue<point>que; point now,next; now.a=0; now.b=0; now.step=0; v[0][0]=true; que.push(now); while (!que.empty()) { now=que.front(); que.pop(); if (now.a==cc || now.b==cc) { printf("%d\n",now.step); for (int i=1;i<=now.step;i++) { if (now.way[i]==1) printf("FILL(1)\n"); if (now.way[i]==2) printf("FILL(2)\n"); if (now.way[i]==3) printf("DROP(1)\n"); if (now.way[i]==4) printf("DROP(2)\n"); if (now.way[i]==5) printf("POUR(1,2)\n"); if (now.way[i]==6) printf("POUR(2,1)\n"); } return ; } //FILL A 111111111 if (now.a!=aa) { next=now; next.a=aa; next.b=now.b; if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=1; que.push(next); } } //FILL B 2222222222 if (now.b!=bb) { next=now; next.a=now.a; next.b=bb; if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=2; que.push(next); } } //DROP A 3333333333 if (now.a!=0) { next=now; next.a=0; next.b=now.b; if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=3; que.push(next); } } //DROP B 444444444444 if (now.b!=0) { next=now; next.a=now.a; next.b=0; if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=4; que.push(next); } } //pour(1,2) 5555555555555 if (now.a!=0) { if (now.a>=bb-now.b) //a 倒满 b { next=now; next.a=now.a-(bb-now.b); next.b=bb; if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=5; que.push(next); } }else if (now.a<bb-now.b) //a 空了 没倒满 b { next=now; next.a=0; next.b=now.b+now.a; if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=5; que.push(next); } } } //POUR(2,1) 6666666666666 if (now.b!=0) { if (now.b>=aa-now.a) { next=now; next.a=aa; next.b=now.b-(aa-now.a); if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=6; que.push(next); } }else if (now.b<aa-now.a) { next=now; next.a=now.a+now.b; next.b=0; if (!v[next.a][next.b]) { v[next.a][next.b]=1; next.step=now.step+1; next.way[next.step]=6; que.push(next); } } } } printf("impossible\n");}int main(){ scanf("%d%d%d",&aa,&bb,&cc); bfs(); return 0;}
BFS/poj 3414 pots
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。