广度优先遍历
每次操作不外乎6种情况，y加满水/y排空水/x加满水/x排空水/y倒入x中(2 cases)/x倒入y中(2 cases)：
y加满水：(cur_x,y).
y排空水:(cur_x,0).
x加满水:(x,cur_y).
x排空水:(0,cur_y).
y倒入x中(2 cases):
假设倒入水的容量为V：则y中剩余：cur_y-V；x中拥有：cur_x+V;
若倒完之后y还有剩余，说明x已满：V=x-cur_x
故在这种情况下：(x,cur_y+cur_x-x)
若倒完之后y空了，说明：V=cur_y,
故在这种情况下:(cur_x+cur_y,0)
x倒入y中(2 cases):
与上面情况相似，得到：
若倒完之后x还有剩余:(cur_x+cur_y-y,y)
若倒完之后x空了:(0,cur_x+cur_y)
这6种情况看作(cur_x,cur_y)的邻居顶点，故可以使用图的BFS/DFS搜索。
def canMeasureWater(self, jug1Capacity, jug2Capacity, targetCapacity):
"""
:type jug1Capacity: int
:type jug2Capacity: int
:type targetCapacity: int
:rtype: bool
"""
x1 = jug1Capacity
x2 = jug2Capacity
z = targetCapacity
queue = deque()
queue.append((0,0))
visited = set()
visited.add((0,0))
while queue:
for _ in range(len(queue)):
x,y = queue.popleft()
if x==z or y==z or x + y == z:
return True
for (nx,ny) in [(x,x2),(x,0),(x1,y),(0,y),(x1,y+x-x1) if x+y>x1 else (x+y,0), (x+y-x2,x2) if x+y>x2 else (0,y+x)]:
if (nx,ny) not in visited:
queue.append((nx,ny))
visited.add((nx,ny))
return False
DFS
def canMeasureWater(self, jug1Capacity, jug2Capacity, targetCapacity):
"""
:type jug1Capacity: int
:type jug2Capacity: int
:type targetCapacity: int
:rtype: bool
"""
x1 = jug1Capacity
x2 = jug2Capacity
z = targetCapacity
visited = set()
def dfs(x,y):
if x==z or y==z or x + y == z:
return True
if (x,y) not in visited:
visited.add((x,y))
for (nx,ny) in [(x,x2),(x,0),(x1,y),(0,y),(x1,y+x-x1) if x+y>x1 else (x+y,0), (x+y-x2,x2) if x+y>x2 else (0,y+x)]:
if (nx,ny) not in visited:
visited.add((nx,ny))
if dfs(nx,ny):
return True
return False
return dfs(0,0)
贝祖定理
ax+by=z 有解当且仅当 z 是 （x,y 的最大公约数的） 倍数。
def canMeasureWater(self, jug1Capacity, jug2Capacity, targetCapacity):
"""
:type jug1Capacity: int
:type jug2Capacity: int
:type targetCapacity: int
:rtype: bool
"""
x = jug1Capacity
y = jug2Capacity
z = targetCapacity
def gcd(x,y):
r = x % y
while r != 0:
x = y
y = r
r = x % y
return y
if x + y < z:
return False
if x==0 or y==0:
return z == 0 or x == z or y == z
return z % gcd(x,y) == 0
