LeetCode-python 365. 水壶问题

题目链接

难度：中等       类型： dfs

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

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

你可以：

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

示例

输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true

解题思路

对于两个水壶x和y，只有6种操作：

1. 把x清空
2. 把y清空
3. 把x装满
4. 把y装满
5. 把x里的水倒进y
6. 把y里的水倒进x

尝试所有的排列组合，就知道能不能行

为了不重复搜索，记录下经历过的状态

代码实现

class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
        stack = [[0, 0]]
        visited = set()

        while stack:
            remain_x, remain_y = stack.pop()
            if remain_x == targetCapacity or remain_y == targetCapacity or remain_x + remain_y == targetCapacity:
                return True
            if (remain_x, remain_y) in visited:
                continue
            # 记录状态
            visited.add((remain_x, remain_y))

            # 所有有可能的操作
            stack.append((jug1Capacity, remain_y))
            stack.append((remain_x, jug2Capacity))
            stack.append((0, remain_y))
            stack.append((max(0, remain_x - (jug2Capacity - remain_y)), min(jug2Capacity, remain_y + remain_x)))
            stack.append((min(jug1Capacity, remain_y + remain_x), max(0, remain_y - (jug1Capacity - remain_x))))
        return False

模板2：

class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
         
        visited = set()

        def dfs(remain_x, remain_y):
            if (remain_x, remain_y) in visited:
                return False
            if remain_x == targetCapacity or remain_y == targetCapacity or remain_x + remain_y == targetCapacity:
                return True

            visited.add((remain_x, remain_y))

            if dfs(jug1Capacity, remain_y) or dfs(remain_x, jug2Capacity) or dfs(0, remain_y) or dfs(remain_x, 0) or dfs(max(0, remain_x - (jug2Capacity - remain_y)), min(jug2Capacity, remain_y + remain_x)) or dfs(min(jug1Capacity, remain_y + remain_x), max(0, remain_y - (jug1Capacity - remain_x))):
                return True
            return False

        
        return dfs(0, 0)