ByteDrift

从倒水问题看深度优先搜索

发表于 更新于 分类于
有两个水壶，容量分别为 A升 和 B 升。水的供应是无限的。如何确定是否有可能使用这两个壶准确得到 target 升 🤔。

水壶倒水问题

  1. 水壶问题

有两个水壶，容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

如果可以得到 targetCapacity 升水，最后请用以上水壶中的一或两个来盛放取得的 targetCapacity 升水。

你可以：

  • 装满任意一个水壶
  • 清空任意一个水壶
  • 从一个水壶向另外一个水壶倒水，直到装满或者倒空

思路

我们需要需要查找最短路径，最少次数类问题往往会用到BFS 广度优先搜索。而对于判断路径是否存在 类的问题则可以用DFS 深度优先搜索。

这里我们将每种状态存入栈中，将其弹出后，由于我们有三种方案，我们需要做选择：

  1. 倒满其中一个
  2. 将其中一个倒入另一个，这里则又分两种情况
    1. 一杯倒完另一杯都没满
    2. 一杯没倒完另一杯就满了

这个过程中一旦有某个杯为target，或者二者之和为target，则说明结构为true。

对于搜索过的状态，我们需排出否则将陷入循环，这里我们想保存所有搜索过的状态，需要将两个水壶的状态编码为一个整数，由于此处最大为10^6，因此我们需用Long存在Set中。

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
class Solution {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
         // 栈
        Deque<int[]> stack = new ArrayDeque<>();

        // HashSet避免重复搜索，如果当前两个壶的状态搜索过就不用搜索了 
        // 由于水壶最大为10^6我们用* 1000001将其编码为long放入set中
        Set<Long> set = new HashSet<>();
    	// 初始状态 0，0
        stack.push(new int[]{0,0});

        while(!stack.isEmpty()) {
            int[] cur = stack.peek();
            // 如果set中包含则直接poll
            if(set.contains(hash(cur[0],cur[1]))) stack.poll();
            else {
                set.add(hash(cur[0],cur[1]));
                // 如果其中一个壶已经为target，或者两个水壶的和为target，则完成
                if(cur[0]==targetCapacity
                   ||cur[1]==targetCapacity
                  ||cur[0]+cur[1]==targetCapacity) return true;
                // 开搜 情况1 倒出 一个壶
                stack.push(new int[]{0,cur[1]});
                stack.push(new int[]{cur[0],0});

                // 情况2 倒满一个水壶
                stack.push(new int[]{jug1Capacity,cur[1]});
                stack.push(new int[]{cur[0],jug2Capacity});

                // 情况3 从一个倒入另一个
                // 1 倒入 2
                if(jug2Capacity-cur[1]>cur[0]) stack.push(new int[]{0,cur[0]+cur[1]});
                else stack.push(new int[]{cur[0]-(jug2Capacity-cur[1]),jug2Capacity});

                // 2 倒入1
                if(jug1Capacity-cur[0]>cur[1]) stack.push(new int[]{cur[0]+cur[1],0});
                else stack.push(new int[]{jug1Capacity,cur[1]-(jug1Capacity-cur[0])});
            }
        }

        return false;
    }

    long hash(int x,int y) {
        return (long)x * 1000001 + y;
    }
}