## 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`

## Rust Solution

```
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);
}
```

Having problems with this solution? Click here to submit an issue on github.