1879. [算法课深度优先搜索] 水壶问题

有两个水壶,容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

如果可以得到 targetCapacity 升水,最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。

你可以:

  • 装满任意一个水壶
  • 清空任意一个水壶
  • 从一个水壶向另外一个水壶倒水,直到装满或者倒空

提示:

  • 0 <= jug1Capacity, jug2Capacity, targetCapacity <= 10^6

输入

输入三个数 jug1Capacity jug2Capacity targetCapacity

输出

输出 true / false

样例

标准输入 复制文本
3 5 4
标准输出 复制文本
true
标准输入 复制文本
2 6 5
标准输出 复制文本
false
标准输入 复制文本
1 2 3
标准输出 复制文本
true
登录以提交代码。
单点时限 10 秒
内存限制 128 MB
提交 1688
通过 778