poj 3414 Pots

发布时间:2017-1-23 22:51:34 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3414 Pots",主要涉及到poj 3414 Pots方面的内容,对于poj 3414 Pots感兴趣的同学可以参考一下。

 很简单的一题,写过倒红酒的人绝对是秒过。 #include<cstdio> #include<cstring> #include<iostream> #define N 101 using namespace std; int a,b,c; bool vis[N][N]; char str[7][11] = {"lala","FILL(1)","FILL(2)","POUR(1,2)","POUR(2,1)","DROP(1)","DROP(2)"}; typedef struct _Node{ int cou,a,b; struct _Node *pre; int way; }Node; Node queue[N*N]; void display(Node n) { if(n.pre==NULL) { printf("%s\n",str[n.way]); } else { display(*n.pre); printf("%s\n",str[n.way]); } } int main(void) { while(scanf("%d %d %d",&a,&b,&c)!=EOF) { int head,tail; memset(vis,false,sizeof(vis)); vis[0][0] = true; Node now,next; now.a = a; now.b = 0; now.cou = 1; now.pre = NULL; now.way = 1;//分别装满2个瓶的情况 next.a = 0; next.b = b; next.cou = 1; next.pre = NULL; next.way = 2; head = 1; tail = 3; vis[a][0] = true; vis[0][b] = true; vis[0][0] = true; queue[1] = now; queue[2] = next; bool flag = false; Node ans; while(!flag) { int count = tail - head; if(count<=0) break; while(count--) { if(queue[head].a==c||queue[head].b==c) { flag = true; ans = queue[head]; break; } Node tmp; tmp.way = 1; tmp.a = a; tmp.b = queue[head].b; tmp.cou = queue[head].cou+1; tmp.pre = &queue[head]; if(!vis[tmp.a][tmp.b]) { vis[tmp.a][tmp.b] = true; queue[tail++] = tmp; } tmp.way = 2; tmp.a = queue[head].a; tmp.b = b; if(!vis[tmp.a][tmp.b]) { vis[tmp.a][tmp.b] = true; queue[tail++] = tmp; } tmp.way = 3; if(queue[head].a+queue[head].b>b) { tmp.a = (queue[head].a+queue[head].b) - b; } else { tmp.a = 0; tmp.b = queue[head].b+queue[head].a; } if(!vis[tmp.a][tmp.b]) { vis[tmp.a][tmp.b] = true; queue[tail++] = tmp; } tmp.way = 4; if(queue[head].a+queue[head].b>a) { tmp.b = (queue[head].a+queue[head].b) - a; tmp.a = a; } else { tmp.b = 0; tmp.a = queue[head].b+queue[head].a; } if(!vis[tmp.a][tmp.b]) { vis[tmp.a][tmp.b] = true; queue[tail++] = tmp; } tmp.way = 5; tmp.a = 0; tmp.b = queue[head].b; if(!vis[tmp.a][tmp.b]) { vis[tmp.a][tmp.b] = true; queue[tail++] = tmp; } tmp.way = 6; tmp.a = queue[head].a; tmp.b = 0; if(!vis[tmp.a][tmp.b]) { vis[tmp.a][tmp.b] = true; queue[tail++] = tmp; } } ++head; } if(flag) { cout<<ans.cou<<endl; display(ans); cout<<endl; } else { cout<<"impossible"<<endl; } } return 0; }

上一篇:GCJ Round 1A 2008 Problem A. Minimum Scalar Product
下一篇:原来OOM的罪魁祸首是C代码---android out of memory(OOM)

相关文章

关键词: poj 3414 Pots

相关评论