class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if x + y < z:
return False
queue = [(0, 0)]
seen = set((0, 0))
while(len(queue) > 0):
a, b = queue.pop(0)
if a ==z or b == z or a + b == z:
return True
states = set()
states.add((x, b))
states.add((a, y))
states.add((0, b))
states.add((a, 0))
states.add((min(x, b + a), 0 if b < x - a else b - (x - a)))
states.add((0 if a + b < y else a - (y - b), min(b + a, y)))
for state in states:
if state in seen:
continue;
queue.append(state)
seen.add(state)
return False
因此这道题可以完全转化为裴蜀定理。还是以题目给的例子x = 3, y = 5, z = 4，我们其实可以表示成3 * 3 - 1 * 5 = 4, 即3 * x - 1 * y = z。我们用 a 和 b 分别表示 3 升的水壶和 5 升的水壶。那么我们可以：
倒满 a（1）
将 a 倒到 b
再次倒满 a（2）
再次将 a 倒到 b（a 这个时候还剩下 1 升）
倒空 b（-1）
将剩下的 1 升倒到 b
将 a 倒满（3）
将 a 倒到 b
b 此时正好是 4 升
上面的过程就是3 * x - 1 * y = z的具体过程解释。
也就是说我们只需要求出 x 和 y 的最大公约数 d，并判断 z 是否是 d 的整数倍即可。
代码
代码支持：Python3，JavaScript
Python Code：
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if x + y < z:
return False
if (z == 0):
return True
if (x == 0):
return y == z
if (y == 0):
return x == z
def GCD(a, b):
smaller = min(a, b)
while smaller:
if a % smaller == 0 and b % smaller == 0:
return smaller
smaller -= 1
return z % GCD(x, y) == 0
JavaScript：
/**
* @param {number} x
* @param {number} y
* @param {number} z
* @return {boolean}
*/
var canMeasureWater = function (x, y, z) {
if (x + y < z) return false;
if (z === 0) return true;
if (x === 0) return y === z;
if (y === 0) return x === z;
function GCD(a, b) {
let min = Math.min(a, b);
while (min) {
if (a % min === 0 && b % min === 0) return min;
min--;
}
return 1;
}
return z % GCD(x, y) === 0;
};
实际上求最大公约数还有更好的方式，比如辗转相除法：
def GCD(a, b):
if b == 0: return a
return GCD(b, a % b)
