(2)（容器分水） 有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：

1. FILL(i)：用水龙头将容器 $i(i \in {1,2})$ 灌满水；
2. DROP(i)：将容器 i 的水倒进下水道；
3. POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。

求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。

试补全程序。

1#include <bits/stdc++.h>2using namespace std;3const int N = 110;4 5int f[N][N];6int ans;7int a, b, c;8int init;9 10int dfs(int x, int y) {11    if (f[x][y] != init)12        return f[x][y];13    if (x == c || y == c)14        return f[x][y] = 0;15    f[x][y] = init - 1;16    f[x][y] = min(f[x][y], dfs(a, y) + 1);17    f[x][y] = min(f[x][y], dfs(x, b) + 1);18    f[x][y] = min(f[x][y], dfs(0, y) + 1);19    f[x][y] = min(f[x][y], dfs(x, 0) + 1);20    int t = min(a - x, y);21    f[x][y] = min(f[x][y], ①);22    t = min(x, b - y);23    f[x][y] = min(f[x][y], ②);24    return f[x][y];25}26 27void go(int x, int y) {28    if (③)29        return;30    if (f[x][y] == dfs(a, y) + 1) {31        cout << "FILL(1)" << endl;32        go(a, y);33    } else if (f[x][y] == dfs(x, b) + 1) {34        cout << "FILL(2)" << endl;35        go(x, b);36    } else if (f[x][y] == dfs(0, y) + 1) {37        cout << "DROP(1)" << endl;38        go (0, y);39    } else if (f[x][y] == dfs(x, 0) + 1) {40        cout << "DROP(2)" << endl;41        go(x, 0);42    } else {43        int t = min(a - x, y);44        if(f[x][y] == ④) {45            cout << "POUR(2,1)" << endl;46            go(x + t, y - t);47        } else {48            t = min(x, b - y);49            if (f[x][y] == ⑤) {50                cout << "POUR(1,2)" << endl;51                go(x - t, y + t);52            } else53                assert(0);54        }55    }56}57 58int main() {59    cin >> a >> b >> c;60    ans = 1 << 30;61    memset(f, 127, sizeof f);62    init = **f;63    if ((ans = dfs (0, 0)) == init - 1)64        cout << "impossible";65    else {66        cout << ans << endl;67        go (0, 0);68    }69}