poj 3414 Pots 广搜（链式存储）

本文主要是介绍poj 3414 Pots 广搜（链式存储），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题意：有两个罐子A,B,可以进行三种操作，

1. FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;//把第i个罐子装满；
2. DROP(i)      empty the pot i to the drain;//把第i个罐子清空；
3. POUR(i,j)    pour from pot i to pot j; after this operation either the potj is full (and there may be some water left in the poti), or the poti is empty (and all its contents have been moved to the potj).//把第i个罐子的水倒入第j个罐子里，当且仅当有一个罐子满了或者有一个罐子空了；

编写程序使得经过n次操作后，有一个罐子里剩c升水；

Sample Input

3 5 4

样例三个数分别代表两个罐子的水体积，和最终要剩的体积数！

2.思路：bfs,此题与以前不同在于链式存储，不是构图。

3.代码：

#include<stdio.h>
#include<string.h>
struct node
{int a;int b;int parent;//记录父节点int level;int op;
} pot[1000000];
//int pre[100];
int stk[1000000];
int visit[205][205];
void output(int p)
{int top=0;stk[0]=p;while(pot[stk[top]].parent!=-1){top++;stk[top]=pot[stk[top-1]].parent;}for(int i=top; i>=0; i--){//printf("####%d\n",pot[stk[i]].op);switch(pot[stk[i]].op){case 0:{printf("DROP(1)\n");}break;case 1:{printf("FILL(1)\n");}break;case 2:{printf("DROP(2)\n");}break;case 3:{printf("FILL(2)\n");}break;case 4:{printf("POUR(1,2)\n");}break;case 5:{printf("POUR(2,1)\n");}break;}}
}void bfs(int A,int B,int C)
{node cur;pot[0].a=0;pot[0].b=0;pot[0].parent=-1;pot[0].level=0;pot[0].op=-1;//pre[0]=-1;int front=0;int rear=1;visit[0][0]=1;int locate=-1,ans;while(front<rear){cur=pot[front++];if(cur.a==C||cur.b==C){ans=cur.level;locate=front-1;//printf("locate=%d\n",locate);break ;}int ta,tb,tp;for(int i=0; i<6; i++){if(i==0){ta=0;tb=cur.b;tp=i;}if(i==1){ta=A;tb=cur.b;tp=i;}if(i==2){tb=0;ta=cur.a;tp=i;}if(i==3){tb=B;ta=cur.a;tp=i;}if(i==4){if((B-cur.b)>=cur.a){ta=0;tb=cur.a+cur.b;tp=i;}else{ta=cur.a-(B-cur.b);tb=B;tp=i;}}if(i==5){if((A-cur.a)>=cur.b){tb=0;ta=cur.a+cur.b;tp=i;}else{ta=A;tb=cur.b-(A-cur.a);tp=i;}}if(visit[ta][tb]==0){visit[ta][tb]=1;node change;change.a=ta;change.b=tb;change.parent=front-1;change.level=cur.level+1;change.op=tp;//printf("%d,%d,%d,%d,%d\n",change.a,change.b,change.parent,change.op,change.level);pot[rear++]=change;}}}if(locate==-1){printf("impossible\n");}else{printf("%d\n",ans);output(locate);}
}
int main()
{int A,B,C;scanf("%d%d%d",&A,&B,&C);memset(visit,0,sizeof(visit));bfs(A,B,C);return 0;
}

 

 

这篇关于poj 3414 Pots 广搜（链式存储）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---