365. Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

```Input: x = 3, y = 5, z = 4
Output: True
```

Example 2:

```Input: x = 2, y = 6, z = 5
Output: False
```

Constraints:

• `0 <= x <= 10^6`
• `0 <= y <= 10^6`
• `0 <= z <= 10^6`

365. Water and Jug Problem
``````struct Solution;
use std::collections::VecDeque;

impl Solution {
fn can_measure_water(x: i32, y: i32, z: i32) -> bool {
if z > x + y {
return false;
}
if z == x || z == y || z == x + y {
return true;
}
let mut visited = vec![false; (x + y) as usize];

let mut queue: VecDeque<i32> = VecDeque::new();
queue.push_back(0);
while let Some(front) = queue.pop_front() {
for diff in [x, y, -x, -y].iter() {
let next = front + diff;
if next == z {
return true;
} else {
if next < x + y && next > 0 && !visited[next as usize] {
visited[next as usize] = true;
queue.push_back(next);
}
}
}
}
false
}
}

#[test]
fn test() {
let x = 3;
let y = 5;
let z = 4;
let res = true;
assert_eq!(Solution::can_measure_water(x, y, z), res);
let x = 2;
let y = 6;
let z = 5;
let res = false;
assert_eq!(Solution::can_measure_water(x, y, z), res);
}
``````