Question

365. Water and Jug Problem

中文文档

Description

You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:

• Fill either jug completely with water.
• Completely empty either jug.
• Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

 

Example 1:

Input: x = 3, y = 5, target = 4

Output: true

Explanation:

Follow these steps to reach a total of 4 liters:

1. Fill the 5-liter jug (0, 5).
2. Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
3. Empty the 3-liter jug (0, 2).
4. Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
5. Fill the 5-liter jug again (2, 5).
6. Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
7. Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).

Reference: The Die Hard example.

Example 2:

Input: x = 2, y = 6, target = 5

Output: false

Example 3:

Input: x = 1, y = 2, target = 3

Output: true

Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.

 

Constraints:

• 1 <= x, y, target <= 103

Solutions

Solution 1: DFS

Let's denote $jug1Capacity$ as $x$, $jug2Capacity$ as $y$, and $targetCapacity$ as $z$.

Next, we design a function $dfs(i, j)$, which represents whether we can get $z$ liters of water when there are $i$ liters of water in $jug1$ and $j$ liters of water in $jug2$.

The execution process of the function $dfs(i, j)$ is as follows:

• If $(i, j)$ has been visited, return $false$.
• If $i = z$ or $j = z$ or $i + j = z$, return $true$.
• If we can get $z$ liters of water by filling $jug1$ or $jug2$, or emptying $jug1$ or $jug2$, return $true$.
• If we can get $z$ liters of water by pouring water from $jug1$ into $jug2$, or pouring water from $jug2$ into $jug1$, return $true$.

The answer is $dfs(0, 0)$.

The time complexity is $O(x + y)$, and the space complexity is $O(x + y)$. Here, $x$ and $y$ are the sizes of $jug1Capacity$ and $jug2Capacity$ respectively.

class Solution:
  def canMeasureWater(self, x: int, y: int, z: int) -> bool:
    def dfs(i: int, j: int) -> bool:
      if (i, j) in vis:
        return False
      vis.add((i, j))
      if i == z or j == z or i + j == z:
        return True
      if dfs(x, j) or dfs(i, y) or dfs(0, j) or dfs(i, 0):
        return True
      a = min(i, y - j)
      b = min(j, x - i)
      return dfs(i - a, j + a) or dfs(i + b, j - b)

    vis = set()
    return dfs(0, 0)

class Solution {
  private Set<Long> vis = new HashSet<>();
  private int x, y, z;

  public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
    x = jug1Capacity;
    y = jug2Capacity;
    z = targetCapacity;
    return dfs(0, 0);
  }

  private boolean dfs(int i, int j) {
    long st = f(i, j);
    if (!vis.add(st)) {
      return false;
    }
    if (i == z || j == z || i + j == z) {
      return true;
    }
    if (dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0)) {
      return true;
    }
    int a = Math.min(i, y - j);
    int b = Math.min(j, x - i);
    return dfs(i - a, j + a) || dfs(i + b, j - b);
  }

  private long f(int i, int j) {
    return i * 1000000L + j;
  }
}

class Solution {
public:
  bool canMeasureWater(int x, int y, int z) {
    using pii = pair<int, int>;
    stack<pii> stk;
    stk.emplace(0, 0);
    auto hash_function = [](const pii& o) { return hash<int>()(o.first) ^ hash<int>()(o.second); };
    unordered_set<pii, decltype(hash_function)> vis(0, hash_function);
    while (stk.size()) {
      auto st = stk.top();
      stk.pop();
      if (vis.count(st)) {
        continue;
      }
      vis.emplace(st);
      auto [i, j] = st;
      if (i == z || j == z || i + j == z) {
        return true;
      }
      stk.emplace(x, j);
      stk.emplace(i, y);
      stk.emplace(0, j);
      stk.emplace(i, 0);
      int a = min(i, y - j);
      int b = min(j, x - i);
      stk.emplace(i - a, j + a);
      stk.emplace(i + b, j - b);
    }
    return false;
  }
};

func canMeasureWater(x int, y int, z int) bool {
  type pair struct{ x, y int }
  vis := map[pair]bool{}
  var dfs func(int, int) bool
  dfs = func(i, j int) bool {
    st := pair{i, j}
    if vis[st] {
      return false
    }
    vis[st] = true
    if i == z || j == z || i+j == z {
      return true
    }
    if dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0) {
      return true
    }
    a := min(i, y-j)
    b := min(j, x-i)
    return dfs(i-a, j+a) || dfs(i+b, j-b)
  }
  return dfs(0, 0)
}