1
class Solution:
2
    def canMeasureWater(
3
        self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int
4
    ) -> bool:
5
        n1, n2, t = jug1Capacity, jug2Capacity, targetCapacity
6
        if n1 == t or n2 == t or n1 + n2 == t:
7
            return True
8
        if n1 + n2 < t:
9
            return False
10
        if n1 < n2:
11
            n1, n2 = n2, n1
12
        stack = []
13
        visited = set()
14
        d = n1 - n2
15
        if d == t:
16
            return True
17
        while d > n2:
18
            d -= n2
19
            if d == t:
20
                return True
21
        stack.append(d)
22
        while stack:
23
            # print(stack)
24
            d = stack.pop()
25
            visited.add(d)
26
            n = n1 + d
27
            if n == t:
28
                return True
29
            n = n1 - d
30
            if n == t:
31
                return True
32
            while n > n2:
33
                n -= n2
34
                if n == t:
35
                    return True
36
            if n < n2 and n not in visited:
37
                stack.append(n)
38
            n = n2 - d
39
            if n == t:
40
                return True
41
            if n not in visited:
42
                stack.append(n)
43
        return False