↓Skip to main content
  1. Posts/

LeetCode-365 水壶问题

·1 min·
Table of Contents

LeetCode-365 水壶问题 #

Solution 1 #

搜索.

代码如下:

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        vis = set()

        @cache
        def f(i, j):
            if (i, j) in vis:
                return False
            vis.add((i, j))
            if i == target or j == target or i + j == target:
                return True
            return (
                f(x, j)
                | f(i, y)
                | f(0, j)
                | f(i, 0)
                | f(i - min(i, y - j), j + min(i, y - j))
                | f(i + min(j, x - i), j - min(j, x - i))
            )
            
        return f(0, 0)