| 2 | |
| 3 | class Solution: |
| 4 | def canMeasureWater(self, x: int, y: int, z: int) -> bool: |
| 5 | stack = [(0, 0)] |
| 6 | self.seen = set() |
| 7 | while stack: |
| 8 | remain_x, remain_y = stack.pop() |
| 9 | if remain_x == z or remain_y == z or remain_x + remain_y == z: |
| 10 | return True |
| 11 | if (remain_x, remain_y) in self.seen: |
| 12 | continue |
| 13 | self.seen.add((remain_x, remain_y)) |
| 14 | # 把 X 壶灌满。 |
| 15 | stack.append((x, remain_y)) |
| 16 | # 把 Y 壶灌满。 |
| 17 | stack.append((remain_x, y)) |
| 18 | # 把 X 壶倒空。 |
| 19 | stack.append((0, remain_y)) |
| 20 | # 把 Y 壶倒空。 |
| 21 | stack.append((remain_x, 0)) |
| 22 | # 把 X 壶的水灌进 Y 壶，直至灌满或倒空。 |
| 23 | stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y))) |
| 24 | # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。 |
| 25 | stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x))) |
| 26 | return False |
| 27 | |
| 28 | |
| 29 | print(Solution().canMeasureWater(2, 6, 7)) |