算法---水壶问题（DFS）

题目

有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

如果可以得到 targetCapacity 升水，最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。

你可以：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1:

输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true
解释：来自著名的 “Die Hard”
示例 2:

输入: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
输出: false
示例 3:

输入: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
输出: true

提示:

1 <= jug1Capacity, jug2Capacity, targetCapacity <= 106

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/water-and-jug-problem
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路

对于每一步，只有以下几种操作情况：
把 X 壶灌满；
把 Y 壶灌满；
把 X 壶倒空；
把 Y 壶倒空
把 X 壶的水灌进 Y 壶，直至灌满或倒空；
把 Y 壶的水灌进 X 壶，直至灌满或倒空；

你可以说我可以一次操作2-3步，比如把 X 壶灌满；把 Y 壶灌满；把 X 壶倒空；
如果你归到一步，算法写起来太复杂，不容易实现。
每一步的原子操作可以最终达到你的三步效果，代码可实现程度高，所以分为这6种基本操作
然后看他们的各种组合去看看是否满足结果

由于每一步可能和后续的状态重复 所以需要用set记录一下之前已经遇到的情况
防止死循环

解决方法

    fun canMeasureWater(jug1Capacity: Int, jug2Capacity: Int, targetCapacity: Int): Boolean {
        val curState = IntArray(2) { 0 }
        val set = mutableSetOf<String>()

        val queue = LinkedList<IntArray>()
        queue.offer(curState)
        while (!queue.isEmpty()) {
            val pop = queue.pop()
            if (set.contains(hash(pop))) {
                continue
            }
            set.add(hash(pop))
            if (pop[0] == targetCapacity || pop[1] == targetCapacity || pop[0] + pop[1] == targetCapacity) {
                return true
            }
            //倒空
            queue.offer(intArrayOf(0, pop[1]))
            queue.offer(intArrayOf(pop[0], 0))
            //装满
            queue.offer(intArrayOf(jug1Capacity, pop[1]))
            queue.offer(intArrayOf(pop[0], jug2Capacity))

            //互相倒
            //1 倒入2
            queue.offer(
                intArrayOf(
                    (pop[0] - (jug2Capacity - pop[1])).coerceAtLeast(0),
                    (pop[1] + pop[0]).coerceAtMost(jug2Capacity)
                )
            )
            //2倒入1
            queue.offer(
                intArrayOf(
                    (pop[0] + pop[1]).coerceAtMost(jug1Capacity),
                    (pop[1] - (jug1Capacity - pop[0])).coerceAtLeast(0)
                )
            )
        }
        return false
    }

    private fun hash(state: IntArray): String {
        return "${state[0]}-${state[1]}"
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

总结

1.三天写出来一道题
两天看题解 第三天10分钟写出来

2.重要的是 每一步要分解成原子操作 不然没有办法思考

3.人的生命是宝贵的，因为上天给予我们每个人的只有一次。生命的这个机会可能长点，可能短点，但放于茫茫宇宙中来说，那肯定是极其短暂的。她就像夜空中的一闪流星匆匆而过，当你还在做着美丽的梦想时，她可能马上或者已经结束了。人的一生该怎样度过？是尽情燃烧，还是纵欲腐朽？是任其流逝，还是苟且偷生……