链接：https://vjudge.net/problem/POJ-3414

Task

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

1.FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap; 2.DROP(i) empty the pot i to the drain; 3.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:

1

3 5 4

output:

1
2
3
4
5
6
7

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

Solution

用结构体node表示桶1和桶2的状态，a和b分别是桶1和2的当前水量，depth是从初始状态变到当前状态的步数，字符串s记录从初始到当前状态的路径。BFS时用visit矩阵来记录某个状态是否被搜索过，两个维度分别是两个桶的水量。 每个节点的子节点对几种情况讨论：FILL(1),FILL(2),DROP(1),DROP(2),POUR(1,2),POUR(2,1)，其中POUR(1,2),POUR(2,1)都要分两种情况：用delta记录从1向2倒的水量，如果delta>=0说明可以填满2，否则填不满。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
int A,B,C;
bool visit[101][101];
int delta;
struct node{
    int a,b,depth;
    string s;
    node(int a, int b, int depth, string s): a(a),b(b),depth(depth),s(s) {}
};
inline string BFS(){
    queue<node> q;
    q.push(node(0,0,0,""));
    visit[0][0]=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        // satisfied
        if(t.a==C || t.b==C){
            printf("%d\n",t.depth);
            return t.s;
        }
        // fill 1 with A, 2 stayed t.b
        if(!visit[A][t.b]){
            visit[A][t.b]=1;
            q.push(node(A, t.b, t.depth+1, t.s+"FILL(1)\n"));
        }
        // fill 2 with B, 1 stayed t.a
        if(!visit[t.a][B]){
            visit[t.a][B]=1;
            q.push(node(t.a, B, t.depth+1, t.s+"FILL(2)\n"));
        }
        // drop 1 with 0, 2 stayed t.b
        if(!visit[0][t.b]){
            visit[0][t.b]=1;
            q.push(node(0, t.b, t.depth+1, t.s+"DROP(1)\n"));
        }
        // drop 2 with 0, 1 stayed t.a
        if(!visit[t.a][0]){
            visit[t.a][0]=1;
            q.push(node(t.a, 0, t.depth+1, t.s+"DROP(2)\n"));
        }
        delta=t.a-(B-t.b);
        // pour 1 to 2 and 2 can be filled
        if(delta>=0){
            if(!visit[delta][B]){
                visit[delta][B]=1;
                q.push(node(delta, B, t.depth+1, t.s+"POUR(1,2)\n"));
            }
        }
        // pour 1 to 2 and 2 cannot be filled
        else{
            if(!visit[0][t.a+t.b]){
                visit[0][t.a+t.b]=1;
                q.push(node(0, t.a+t.b, t.depth+1, t.s+"POUR(1,2)\n"));
            }
        }
        delta=t.b-(A-t.a);
        // pour 2 to 1 and 1 can be filled
        if(delta>=0){
            if(!visit[A][delta]){
                visit[A][delta]=1;
                q.push(node(A, delta, t.depth+1, t.s+"POUR(2,1)\n"));
            }
        }
        // pour 2 to 1 and 1 cannot be filled
        else{
            if(!visit[t.a+t.b][0]){
                visit[t.a+t.b][0]=1;
                q.push(node(t.a+t.b, 0, t.depth+1, t.s+"POUR(2,1)\n"));
            }
        }
    }
    return "impossible";
}
int main(){
    scanf("%d %d %d",&A,&B,&C);
    string result=BFS();
    printf("%s",result.c_str());
    return 0;
}