Pots
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 10300Accepted: 4362Special Judge
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 potj; 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).
Write a program to find the shortest possible sequence of these operations that will yield exactlyC 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 andC≤max(A,B).
Output
The first line of the output must contain the length of the sequence of operationsK. The followingK 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
6FILL(2)POUR(2,1)DROP(1)POUR(2,1)FILL(2)POUR(2,1)
Source
, Western Subregion
题目链接：?id=3414题目大意：两个杯子容积为A和B，三类操作，装满，倒光，一个杯子倒到另一个杯子里(倒的时候是尽可能将另一个杯子倒满，倒水的杯子可以有剩余)，求最小的操作次数能使其中一个杯子中水的体积为C题目分析：求最小操作次数并输出，，BFS，三类操作，六种情况，分别讨论，vis[a][b]记录某第一个杯子a体积水和第二个杯子b体积水的情况有没有出现过，本题主要难在输出，开始用一维pre数组标记，发现行不通，因为设pre[a] = b是b在a之后操作，则若出现循环操作例如pre[2]=1,pre[1] = 2则程序会死循环，因此改用二维数组标记pre[step][a] = b，表示在第step步时b是a之后的操作，最后逆序输出即可代码依旧奇丑无比
#include <cstdio>#include <queue>#include <cstring>using namespace std;int A, B, C, ans;int re[100000], cnt = 0;bool vis[105][105];char out[7][10] = {"","FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};struct NUM{int a, b; //a, b表示两个杯子中水的体积int step; //step表示操作次数int now; //now表示当前的操作序号int pre[5000][10]; //pre记录顺序};void BFS(){memset(vis, false, sizeof(vis));queue<NUM> q;NUM st, t, cur;memset(st.pre, 0, sizeof(st.pre));st.a = 0;st.b = 0;st.step = 0;st.now = 0;q.push(st);while(!q.empty()){t = q.front();cur = t;q.pop();if(t.a == C || t.b == C){printf("%d\n", t.step);while(t.now) //迭代得到操作序列{re[cnt++] = t.now;t.now = t.pre[t.step–][t.now];}return;}for(int i = 1; i <= 6; i++){t = cur; //每次要将t还原！if(i == 1)//fill(1){t.now = 1;t.a = A;t.step ++;if(!vis[t.a][t.b]){vis[t.a][t.b] = true;t.pre[t.step][t.now] = cur.now;q.push(t);}}if(i == 2) //fill(2){t.now = 2;t.b = B;t.step ++;if(!vis[t.a][t.b]){vis[t.a][t.b] = true;t.pre[t.step][t.now] = cur.now;q.push(t);}}if(i == 3) // drop(1){t.now = 3;t.a = 0;t.step ++;if(!vis[t.a][t.b]){vis[t.a][t.b] = true;t.pre[t.step][t.now] = cur.now;q.push(t);}}if(i == 4)//drop(2){t.now = 4;t.b = 0;t.step ++;if(!vis[t.a][t.b]){vis[t.a][t.b] = true;t.pre[t.step][t.now] = cur.now;q.push(t);}}if(i == 5)//pour(1,2){t.now = 5;int tmp = t.b;if(t.b + t.a >= B){t.b = B;t.a -= (B – tmp);}else{t.b += t.a;t.a = 0;}t.step ++;if(!vis[t.a][t.b]){vis[t.a][t.b] = true;t.pre[t.step][t.now] = cur.now;q.push(t);}}if(i == 6) //pour(2,1){t.now = 6;int tmp = t.a;if(t.b + t.a >= A){t.a = A;t.b -= (A – tmp);}else{t.a += t.b;t.b = 0;}t.step ++;if(!vis[t.a][t.b]){vis[t.a][t.b] = true;t.pre[t.step][t.now] = cur.now;q.push(t);}}}}ans = -1;return;}int main(){scanf("%d %d %d", &A, &B, &C);BFS();if(ans == -1)printf("impossible\n");elsefor(int i = cnt – 1; i >= 0; i–)printf("%s\n", out[re[i]]);}
平平淡淡才是真
