leecode/daily/2019-09-15.md

# 毎日一题 -  水壶问题

## 信息卡片

* 时间：2019-09-15
* 题目链接：https://leetcode-cn.com/problems/water-and-jug-problem/
* tag：`Math`  
## 题目描述
```
给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。
```

## 参考答案

1.数学分析解答

上面的问题是一个特例，我们可以抽象为[leetcode-365-水壶问题](https://leetcode-cn.com/problems/water-and-jug-problem/)。
```
有两个容量分别为 x升 和 y升 的水壶（壶1，壶2）以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
```

解题核心思路（x < y，即壶1容量小于壶2，x == y的情况后面讨论）：

1. 将壶2倒满，往壶1倒入至满。
2. 若壶1满，记录当前壶2中新水量。壶1倒出，将壶2中剩余的继续往壶1中倒入；（当壶1满，继续此操作，并记录当前壶2中新水量nw， 若此新水量已被记录，则）。
3. 若出现壶1不满时（即此时壶2必空），重复操作1。

开辟一个新数组nws记录所有新水量，对任意nws[i]，可构造的水量为nws[i]，nws[i]+x，nws[i]+y。

（其实不需要新数组，因为数学上可以证明新水量的值循环周期呈现，故可以使用一个临时变量cur，当cur==x为终止条件）

数学证明新水量nw值是循环周期的：
![1111](<https://raw.githubusercontent.com/lvguofeng1303/markdownimage/master/daily/%E6%B0%B4%E5%A3%B6%E9%97%AE%E9%A2%98/math%20prove.jpg>)

个别特殊情况考虑：

- x == z || y == z;  **true**
- x == 0 || x+y < z;  **false**
- x+y == z || z == 0;  **true**

```c++
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。

```c++
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;
    }
};
```

## 优秀解答

>暂缺