(容器分水) 有两个容器,容器 1 的容量为为 a 升,容器 2 的容量为 b 升;同时允 许下列的三种操作,分别为:
1) FILL(i):用水龙头将容器 i (i∈{1,2})灌满水;
2) DROP(i):将容器 i 的水倒进下水道;
3) 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); } } }
①处应填( )
dfs(x + t, y - t) + 1
dfs(x + t, y - t) - 1
dfs(x - t, y + t) + 1
dfs(x - t, y + t) - 1
②处应填( )
dfs(x + t, y - t) + 1
dfs(x + t, y - t) - 1
dfs(x - t, y + t) + 1
dfs(x - t, y + t) - 1
③处应填( )
x==c||y==c
x==c&&y==c
x>=c||y>=c
x>=c&&y>=c
④处应填( )
dfs(x+t,y-t)+1
dfs(x+t,y-t)-1
dfs(x-t,y+t)+1
dfs(x-t,y+t)-1
⑤处应填( )
dfs(x+t,y-t)+1
dfs(x+t,y-t)-1
dfs(x-t,y+t)+1
dfs(x-t,y+t)-1