- 时间：2019-09-15
- 题目链接：https://leetcode-cn.com/problems/water-and-jug-problem/
- tag：
Math
给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。
1.数学分析解答
上面的问题是一个特例，我们可以抽象为leetcode-365-水壶问题。
有两个容量分别为 x升 和 y升 的水壶（壶1，壶2）以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
解题核心思路（x < y，即壶1容量小于壶2，x == y的情况后面讨论）：
- 将壶2倒满，往壶1倒入至满。
- 若壶1满，记录当前壶2中新水量。壶1倒出，将壶2中剩余的继续往壶1中倒入；（当壶1满，继续此操作，并记录当前壶2中新水量nw， 若此新水量已被记录，则）。
- 若出现壶1不满时（即此时壶2必空），重复操作1。
开辟一个新数组nws记录所有新水量，对任意nws[i]，可构造的水量为nws[i]，nws[i]+x，nws[i]+y。
（其实不需要新数组，因为数学上可以证明新水量的值循环周期呈现，故可以使用一个临时变量cur，当cur==x为终止条件）
数学证明新水量nw值是循环周期的：
个别特殊情况考虑：
- x == z || y == z; true
- x == 0 || x+y < z; false
- x+y == z || z == 0; true
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(x > y) return canMeasureWater(y, x, z);
if(x == z || y == z) return true;
if(x == 0 || x+y < z) return false;
if(x+y == z || z == 0) return true;
int cur = y - x;
while(cur != x){
if(cur == z) return true;
if(cur > x){
if(cur + x == z) return true;
cur = cur - x;
}
else{
if(cur + y == z || cur + x == z) return true;
cur = y - x + cur;
}
}
return false;
}
};2.BFS
不仅可以计算是否能获取 z 升水，而且可以获得最少多少操作可获取 z 升水。（缺点，无法通过，因为需要太大的空间，需要申请一个三维数组记录状态）
核心思想就是状态转移问题：
壶0（x+y），壶1（x），壶2（y），壶0是本是无限大水池，同理于定义为大小为x+y的壶。用bfs的思想，使用一个队列记录所有新的状态。
对于任意状态（c，a，b），状态转移就是：
- 若c不为0，将壶0倒水入壶1或壶2；若a不为0，将壶1倒水入壶0或壶2；若b不为0，将壶2倒水入壶0或壶1；
- 记录每个新状态，并入队，若此状态访问过则不入队。
特殊情况考虑同1。
class Solution {
public:
struct state{
int nums[3];
state(int xy, int x, int y){
nums[0] = xy;
nums[1] = x;
nums[2] = y;
}
};
state pour_water(state cur, int src, int det, int size[]){
state ans = cur;
int need_w = size[det] - cur.nums[det];
if(need_w <= cur.nums[src]){
ans.nums[det] += need_w;
ans.nums[src] -= need_w;
}
else{
ans.nums[det] += ans.nums[src];
ans.nums[src] = 0;
}
return ans;
}
bool canMeasureWater(int x, int y, int z) {
if(x > y) return canMeasureWater(y, x, z); //
if(x == z || y == z) return true;
if(x == 0 || x+y < z) return false;
if(x+y == z || z == 0) return true;
int visited[x+y+1][x+1][y+1];
int water_size[3] = {x+y, x, y};
memset(visited, 0, sizeof(visited));
state cur(x+y, 0, 0);
queue<state> q;
q.push(cur);
int step = 0;
while(!q.empty()){
int size = q.size();
while(size){
state temp(0, 0, 0);
cur = q.front();
if(cur.nums[1] + cur.nums[2] == z) return true;
visited[cur.nums[0]][cur.nums[1]][cur.nums[2]] = 1;
q.pop();
if(cur.nums[0] != 0){
temp = pour_water(cur, 0, 1, water_size);
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
q.push(temp);
temp = pour_water(cur, 0, 2, water_size);
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
q.push(temp);
}
if(cur.nums[1] != 0){
temp = pour_water(cur, 1, 2, water_size);
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
q.push(temp);
temp = pour_water(cur, 1, 0, water_size);
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
q.push(temp);
}
if(cur.nums[2] != 0){
temp = pour_water(cur, 2, 1, water_size);
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
q.push(temp);
temp = pour_water(cur, 2, 0, water_size);
if(visited[temp.nums[0]][temp.nums[1]][temp.nums[2]] != 1)
q.push(temp);
}
size--;
}
step++;
}
return false;
}
};暂缺