(2)（容器分水） 有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：
- FILL(i)：用水龙头将容器 i(i \in {1,2})i(i∈1,2) 灌满水；
- DROP(i)：将容器 i 的水倒进下水道；
- POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。
求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。
试补全程序。
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 110;
- int f[N][N];
- int ans;
- int a, b, c;
- int init;
- int dfs(int x, int y) {
- if (f[x][y] != init)
- return f[x][y];
- if (x == c || y == c)
- return f[x][y] = 0;
- f[x][y] = init - 1;
- f[x][y] = min(f[x][y], dfs(a, y) + 1);
- f[x][y] = min(f[x][y], dfs(x, b) + 1);
- f[x][y] = min(f[x][y], dfs(0, y) + 1);
- f[x][y] = min(f[x][y], dfs(x, 0) + 1);
- int t = min(a - x, y);
- f[x][y] = min(f[x][y], ①);
- t = min(x, b - y);
- f[x][y] = min(f[x][y], ②);
- return f[x][y];
- }
- void go(int x, int y) {
- if (③)
- return;
- if (f[x][y] == dfs(a, y) + 1) {
- cout << "FILL(1)" << endl;
- go(a, y);
- } else if (f[x][y] == dfs(x, b) + 1) {
- cout << "FILL(2)" << endl;
- go(x, b);
- } else if (f[x][y] == dfs(0, y) + 1) {
- cout << "DROP(1)" << endl;
- go (0, y);
- } else if (f[x][y] == dfs(x, 0) + 1) {
- cout << "DROP(2)" << endl;
- go(x, 0);
- } else {
- int t = min(a - x, y);
- if(f[x][y] == ④) {
- cout << "POUR(2,1)" << endl;
- go(x + t, y - t);
- } else {
- t = min(x, b - y);
- if (f[x][y] == ⑤) {
- cout << "POUR(1,2)" << endl;
- go(x - t, y + t);
- } else
- assert(0);
- }
- }
- }
- int main() {
- cin >> a >> b >> c;
- ans = 1 << 30;
- memset(f, 127, sizeof f);
- init = **f;
- if ((ans = dfs (0, 0)) == init - 1)
- cout << "impossible";
- else {
- cout << ans << endl;
- go (0, 0);
- }
- }
①～⑤处应填（ ）
1.
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
2.
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
3.
A. x == c || y == c
B. x == c && y == c
C. x >= c || y >= c
D. x >= c && y >= c
4.
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
5.
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
