Pots

Time Limit: 1000MS Memory Limit: 65536K

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

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

题目大意

给定一个容量为 a 的罐子1和一个容量为 b 的罐子2，有六种操作：
（1）装满罐子 1，FILL(1) ；
（2）装满罐子 2，FILL(2) ；
（3）将罐子 1 倒空，DROP(1) ；
（4）将罐子 2 倒空，DROP(2) ；
（5）将罐子 1 倒入罐子 2，直至罐子 1 为空或者罐子 2 已满，POUR(1, 2) ；
（5）将罐子 2 倒入罐子 1，直至罐子 2 为空或者罐子 1 已满，POUR(2, 1) 。

求其中一个罐子达到容量 c 的最小步数以及具体步骤。

解题思路

明显的BFS求最短步数模型，不过有些细节需要注意，进行罐子互相倾倒的操作时需要注意边界，而且罐子的操作需要一一对应。其它地方基本上都是套用模板，总的来说还是简单题。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

const int N = 110;
struct node{
    int x, y;    //记录两个瓶子状态
    string s;    //记录到达状态的所有操作
};
string ops[6] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int dist[N][N], a, b, c;

void bfs(){
    memset(dist, 0x3f, sizeof(dist));
    node src = {0, 0, ""};
    queue<node> q; q.push(src);
    dist[0][0] = 0;

    while(!q.empty()){
        node cur = q.front();
        q.pop();

        int d = dist[cur.x][cur.y], x = cur.x, y = cur.y;
        //已经出现有一个瓶子达到c
        if(x == c || y == c){
            cout << d << endl;
            for(int i = 0; i < (int)cur.s.size(); i ++ ) cout << ops[cur.s[i] - '0'] << endl;
            return;
        }

        int t1 = min(x, b - y), t2 = min(a - x, y);  //瓶子1与瓶子2相互倒
        int dx[6] = {a - x, 0, -x, 0, -t1, t2};      //与ops一一对应
        int dy[6] = {0, b - y, 0, -y, t1, -t2};

        for(int k = 0; k < 6; k ++ ){
            int nx = x + dx[k], ny = y + dy[k];
            if(dist[nx][ny] == inf){   //每个状态至多访问一次
                char op = '0' + k;
                string ns = cur.s + op;
                node to = {nx, ny, ns};
                q.push(to);
                dist[nx][ny] = d + 1;
            }
        }
    }

    cout << "impossible" << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> a >> b >> c;

    bfs();

    return 0;
}