| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
Medium |
|
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:
- Fill the 5-liter jug (0, 5).
- Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
- Empty the 3-liter jug (0, 2).
- Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
- Fill the 5-liter jug again (2, 5).
- 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).
- 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
Let's denote
Next, we design a function
The execution process of the function
- 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
The time complexity is
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)
}