Pots（BFS）

Pots

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 31 Accepted Submission(s) : 14

Special Judge

Problem Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
DROP(i) empty the pot i to the drain;
POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

FILL(2)

POUR(2,1)

DROP(1)

POUR(2,1)

FILL(2)

POUR(2,1)

Source

PKU

题意：给出不定数量的样例，每个样例一行，有三个整数，a，b，c，a和b代表两个杯子的容量，c是希望得到的液体体积，一开始两个杯子都是空的，如果利用两个杯子可以倒出c则输出最小的步数和倒出c的步骤；

对两个杯子可以进行以下操作：

FILL(i)：装满第i个杯子；

POUR(i，j)：从第i个杯子向第j个杯子中倒水；

DROP(i)：清空第i个杯子；

思路：

利用BFS进行搜索，求出最小部属并输出；注意对于每一个状态都可能有六种操作，在进行每一种操作前都要进行判断该操作可以进行吗。

AC代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 
  6 
  7 using namespace std;
  8 struct node
  9 {
 10     int aa;
 11     int bb;
 12     int sgin;//父亲节点
 13     int sp;//父亲节点到该点的操作
 14 };
 15 int a,b,c;
 16 int ff=0;
 17 node sk[10005];//队列
 18 bool sg[105][105];//记录节点的访问属性
 19 int kiss[10005];//记录操作
 20 
 21 void s1(node &s,int m)//操作1：把a倒满
 22 {
 23     s.aa=a;
 24     s.sgin=m;//记录下父亲节点的位置
 25     s.sp=1;//记录下有父亲节点到达该点的操作
 26 }
 27 void s2(node &s,int m)//操作2：把b倒满
 28 {
 29     s.bb=b;
 30     s.sgin=m;
 31     s.sp=2;
 32 }
 33 void s3(node &s,int m)//操作3：把a清空
 34 {
 35     s.aa=0;
 36     s.sgin=m;
 37     s.sp=3;
 38 }
 39 void s4(node &s,int m)//操作4：把b清空
 40 {
 41     s.bb=0;
 42     s.sgin=m;
 43     s.sp=4;
 44 }
 45 void s5(node &s,int m)//操作5：从a中向b中到溶液
 46 {
 47     if(s.aa+s.bb<=b){
 48         s.bb+=s.aa;
 49         s.aa=0;
 50         s.sgin=m;
 51         s.sp=5;
 52     }
 53     else{
 54         s.aa=s.aa-(b-s.bb);
 55         s.bb=b;
 56         s.sgin=m;
 57         s.sp=5;
 58     }
 59 }
 60 void s6(node &s,int m)//操作6：从b中向a中到溶液
 61 {
 62     if(s.bb+s.aa<=a){
 63         s.aa+=s.bb;
 64         s.bb=0;
 65         s.sgin=m;
 66         s.sp=6;
 67     }
 68     else{
 69         s.bb=s.bb-(a-s.aa);
 70         s.aa=a;
 71         s.sgin=m;
 72         s.sp=6;
 73     }
 74 }
 75 
 76 int ss(node x)//找出步骤
 77 {
 78     while(1){
 79         if(x.sp==0)
 80             break;
 81         kiss[ff++]=x.sp;
 82         x=sk[x.sgin];
 83     }
 84     return 0;
 85 }
 86 
 87 int bfs()
 88 {
 89     sk[0].aa=0;//初始化条件
 90     sk[0].bb=0;
 91     sk[0].sgin=0;
 92     sk[0].sp=0;//挑出步骤的跳出条件
 93     sg[0][0]=true;
 94     int le=0,ri=1;
 95     while(le<ri){
 96         node x=sk[le];
 97         if(x.aa==c||x.bb==c){//利用两个杯子倒出了容量c
 98             ss(x);
 99             return 1;//利用两个杯子可以倒出容量c，则返回1
100         }
101         if(x.aa!=a){//进行操作1时要判断a是否是满的，如果a是满的则不可以进行操作1
102             s1(x,le);
103             if(sg[x.aa][x.bb]==false){//操作1进行后，产生了新的点，检验该点被访问你过吗，若果该点别访问过着不可以插入到队列了面
104                 sk[ri++]=x;
105                 sg[x.aa][x.bb]=true;
106             }
107             x=sk[le];
108         }
109         if(x.bb!=b){//如果b是满的则不可以进行操作2
110             s2(x,le);
111             if(sg[x.aa][x.bb]==false){//操作2进行后，产生了新的点，检验该点被访问你过吗，若果该点别访问过着不可以插入到队列了面
112                 sk[ri++]=x;
113                 sg[x.aa][x.bb]=true;
114             }
115             x=sk[le];
116         }
117         if(x.aa!=0){//如果a是空的则不可以进行操作3
118             s3(x,le);
119             if(sg[x.aa][x.bb]==false){//操作3进行后，产生了新的点，检验该点被访问你过吗，若果该点别访问过着不可以插入到队列了面
120                 sk[ri++]=x;
121                 sg[x.aa][x.bb]=true;
122             }
123             x=sk[le];
124         }
125         if(x.bb!=0){//如果b是空的则不可以进行操作4
126             s4(x,le);
127             if(sg[x.aa][x.bb]==false){//操作4进行后，产生了新的点，检验该点被访问你过吗，若果该点别访问过着不可以插入到队列了面
128                 sk[ri++]=x;
129                 sg[x.aa][x.bb]=true;
130             }
131             x=sk[le];
132         }
133         if(x.aa!=0){//如果a是空的则不可以进行操作5
134             s5(x,le);
135             if(sg[x.aa][x.bb]==false){//操作5进行后，产生了新的点，检验该点被访问你过吗，若果该点别访问过着不可以插入到队列了面
136                 sk[ri++]=x;
137                 sg[x.aa][x.bb]=true;
138             }
139             x=sk[le];
140         }
141         if(x.bb!=0){//如果b是空的则不可以进行操作6
142             s6(x,le);
143             if(sg[x.aa][x.bb]==false){//操作6进行后，产生了新的点，检验该点被访问你过吗，若果该点别访问过着不可以插入到队列了面
144                 sk[ri++]=x;
145                 sg[x.aa][x.bb]=true;
146             }
147         }
148         le++;
149     }
150     return 0;//利用两个杯子不可以倒出容量c，则返回0；
151 }
152 
153 int main()
154 {
155 //    freopen("input.txt","r",stdin);
156     while(cin>>a>>b>>c){
157         memset(sg,false,sizeof(sg));
158         memset(kiss,0,sizeof(kiss));
159         ff=0;
160         int skn=bfs();
161         if(skn==1){
162             cout<<ff<<endl;
163             ff--;
164             while(ff>=0)
165             {
166                 if(kiss[ff]==1){
167                     cout<<"FILL(1)"<<endl;
168                 }
169                 if(kiss[ff]==2){
170                     cout<<"FILL(2)"<<endl;
171                 }
172                 if(kiss[ff]==3){
173                     cout<<"DROP(1)"<<endl;
174                 }
175                 if(kiss[ff]==4){
176                     cout<<"DROP(2)"<<endl;
177                 }
178                 if(kiss[ff]==5){
179                     cout<<"POUR(1,2)"<<endl;
180                 }
181                 if(kiss[ff]==6){
182                     cout<<"POUR(2,1)"<<endl;
183                 }
184                 ff--;
185             }
186         }
187         else{
188             cout<<"impossible"<<endl;
189         }
190     }
191     return 0;
192 }

View Code

网上他人的代码：

 1 #include<iostream>
 2 #include<string>
 3 #include<cstdio>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 const int maxn=110;
 9 
10 string op[7]={"","FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(2,1)","POUR(1,2)"};
11 
12 int l,r;
13 int a,b,c;
14 int vis[maxn][maxn],step[maxn*maxn];
15 
16 struct node{
17     int x,y;
18     int opr;
19     int pre;
20 }info[maxn*maxn];
21 
22 void Solve(int x,int y,int opr){
23     if(vis[x][y])
24         return ;
25     vis[x][y]=1;
26     info[r].x=x;
27     info[r].y=y;
28     info[r].opr=opr;
29     info[r].pre=l;
30     r++;
31 }
32 
33 void Print(){
34     int ans=0;
35     while(l!=0){
36         step[ans++]=info[l].opr;
37         l=info[l].pre;
38     }
39     printf("%d
",ans);
40     for(int i=ans-1;i>=0;i--)
41         cout<<op[step[i]]<<endl;
42 }
43 
44 void BFS(){
45     info[0].x=0;
46     info[0].y=0;
47     vis[0][0]=1;
48     l=0;
49     r=1;
50     int tx,ty;
51     while(l!=r){
52         if(info[l].x==c || info[l].y==c){
53             Print();
54             return ;
55         }
56 
57         tx=a;
58         ty=info[l].y;
59         Solve(tx,ty,1);
60 
61         tx=info[l].x;
62         ty=b;
63         Solve(tx,ty,2);
64 
65         tx=0;
66         ty=info[l].y;
67         Solve(tx,ty,3);
68 
69         tx=info[l].x;
70         ty=0;
71         Solve(tx,ty,4);
72 
73         tx=info[l].x+min(a-info[l].x,info[l].y);
74         ty=info[l].y-min(a-info[l].x,info[l].y);
75         Solve(tx,ty,5);
76 
77         tx=info[l].x-min(b-info[l].y,info[l].x);
78         ty=info[l].y+min(b-info[l].y,info[l].x);
79         Solve(tx,ty,6);
80 
81         l++;
82     }
83     if(l>=r)
84         printf("impossible
");
85 }
86 
87 int main(){
88 
89     //freopen("input.txt","r",stdin);
90 
91     while(~scanf("%d%d%d",&a,&b,&c)){
92         memset(vis,0,sizeof(vis));
93         BFS();
94     }
95     return 0;
96 }

View Code