365. Water and Jug Problem

,

BFS

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
    private static class State {
        private final int jug1;
        private final int jug2;

        public State(int jug1, int jug2) {
            this.jug1 = jug1;
            this.jug2 = jug2;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            State state = (State) o;
            return jug1 == state.jug1 && jug2 == state.jug2;
        }

        @Override
        public int hashCode() {
            return Objects.hash(jug1, jug2);
        }
    }

    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (jug1Capacity + jug2Capacity < targetCapacity) {
            return false;
        }

        State initialState = new State(0, 0);

        Set<State> visitedSet = new HashSet<>();
        Queue<State> queue = new LinkedList<>();

        queue.offer(initialState);
        visitedSet.add(initialState);

        while (!queue.isEmpty()) {
            State state = queue.poll();

            if (state.jug1 == targetCapacity || state.jug2 == targetCapacity || state.jug1 + state.jug2 == targetCapacity) {
                return true;
            }

            // 枚举可能转换到的下一个状态

            // 填满 jug1
            toNextState(queue, visitedSet, new State(jug1Capacity, state.jug2));

            // 填满 jug2
            toNextState(queue, visitedSet, new State(state.jug1, jug2Capacity));

            // 清空 jug1
            toNextState(queue, visitedSet, new State(0, state.jug2));

            // 清空 jug2
            toNextState(queue, visitedSet, new State(state.jug1, 0));

            // 从 jug1 向 jug2 倒水，直至装满
            if (state.jug1 >= jug2Capacity - state.jug2) {
                toNextState(queue, visitedSet, new State(state.jug1 - (jug2Capacity - state.jug2), jug2Capacity));
            }

            // 从 jug1 向 jug2 倒水，直至倒空
            toNextState(queue, visitedSet, new State(0, Math.min(jug2Capacity, state.jug2 + state.jug1)));

            // 从 jug2 向 jug1 倒水，直至装满
            if (state.jug2 >= jug1Capacity - state.jug1) {
                toNextState(queue, visitedSet, new State(jug1Capacity, state.jug2 - (jug1Capacity - state.jug1)));
            }

            // 从 jug2 向 jug1 倒水，直至倒空
            toNextState(queue, visitedSet, new State(Math.min(jug1Capacity, state.jug1 + state.jug2), 0));
        }

        return false;
    }

    private void toNextState(Queue<State> queue, Set<State> visitedSet, State nextState) {
        if (!visitedSet.contains(nextState)) {
            queue.offer(nextState);
            visitedSet.add(nextState);
        }
    }
}

DFS

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        // 暴力搜索
        // 可使用如下动作：
        // 1. 装满 A
        // 2. 清空 A
        // 3. 装满 B
        // 4. 清空 B
        // 5. 从 A 倒向 B, 倒空 A
        // 6. 从 A 倒向 B, 装满 B
        // 7. 从 B 倒向 A, 倒空 B
        // 8. 从 B 倒向 A, 装满 A

        int waters1 = 0, waters2 = 0;

        Map<Integer, Set<Integer>> visitedMap = new HashMap<>();
        return dfs(visitedMap, waters1, waters2, jug1Capacity, jug2Capacity, targetCapacity);
    }

    private boolean dfs(Map<Integer, Set<Integer>> visitedMap, int waters1, int waters2, int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (waters1 + waters2 == targetCapacity) {
            return true;
        }

        if (visitedMap.getOrDefault(waters1, Collections.emptySet()).contains(waters2)) {
            return false;
        }

        visitedMap.computeIfAbsent(waters1, k -> new HashSet<>()).add(waters2); // 注意在检查未被访问后就立刻标记，避免重复检查导致栈溢出

        if (dfs(visitedMap, jug1Capacity, waters2, jug1Capacity, jug2Capacity, targetCapacity)) {
            return true;
        }
        if (dfs(visitedMap, 0, waters2, jug1Capacity, jug2Capacity, targetCapacity)) {
            return true;
        }
        if (dfs(visitedMap, waters1, jug2Capacity, jug1Capacity, jug2Capacity, targetCapacity)) {
            return true;
        }
        if (dfs(visitedMap, waters1, 0, jug1Capacity, jug2Capacity, targetCapacity)) {
            return true;
        }

        int remain2 = jug2Capacity - waters2;
        if (waters1 >= remain2) {
            if (dfs(visitedMap, waters1 - remain2, jug2Capacity, jug1Capacity, jug2Capacity, targetCapacity)) {
                return true;
            }
        } else {
            if (dfs(visitedMap, 0, waters2 + waters1, jug1Capacity, jug2Capacity, targetCapacity)) {
                return true;
            }
        }

        int remain1 = jug1Capacity - waters1;
        if (waters2 >= remain1) {
            if (dfs(visitedMap, jug1Capacity, waters2 - remain1, jug1Capacity, jug2Capacity, targetCapacity)) {
                return true;
            }
        } else {
            if (dfs(visitedMap, waters1 + waters2, 0, jug1Capacity, jug2Capacity, targetCapacity)) {
                return true;
            }
        }

        return false;
    }
}

References

365. Water and Jug Problem