1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| func canMeasureWater(jug1Capacity int, jug2Capacity int, targetCapacity int) bool {
set := make(map[string]bool)
var dfs func(x, y int) bool
dfs = func(x, y int) bool {
if x == targetCapacity || y == targetCapacity || x+y == targetCapacity {
return true
}
numStr := strconv.Itoa(x) + "," + strconv.Itoa(y)
if set[numStr] {
return false
}
set[numStr] = true
return dfs(jug1Capacity, y) || dfs(0, y) ||
dfs(x, jug2Capacity) || dfs(x, 0) ||
dfs(x-min(x, jug2Capacity-y), y+min(x, jug2Capacity-y)) ||
dfs(x+min(y, jug1Capacity-x), y-min(y, jug1Capacity-x))
}
return dfs(0, 0)
}
func min(num1, num2 int) int {
if num1 <= num2 {
return num1
}
return num2
}
|
