LeetCode 365. 水壶问题

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 *z升 *水。

你允许：

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

示例 1:
输入: x = 3, y = 5, z = 4
输出: True

示例 2:
输入: x = 2, y = 6, z = 5
输出: False

class Solution {

    private static class Status{
        public int a, b;
        public Status(int a, int b){
            this.a = a;
            this.b = b;
        }

        @Override
        public boolean equals(Object o) {
            if (o == null || getClass() != o.getClass()) return false;
            Status status = (Status) o;
            return a == status.a && b == status.b;
        }

        @Override
        public int hashCode() {
            return a * 1000 + b;
        }
    }

    public boolean canMeasureWater(int x, int y, int z) {
        Set<Status> setStatus = new HashSet<>();
        Queue<Status> queue = new LinkedList<>();
        Set<Integer> setResult = new HashSet<>();

        Status curStatus = new Status(0, 0);
        setResult.add(0);
        setStatus.add(curStatus);
        queue.add(curStatus);

        while(!queue.isEmpty()){
            curStatus = queue.poll();
            int a = curStatus.a;
            int b = curStatus.b;
            setResult.add(a);
            setResult.add(b);
            setResult.add(a + b);
            if(setResult.contains(z)) return true;

            //装满第一个杯子
            if(a != x){
                if(!setStatus.contains(new Status(x, b))) {
                    queue.add(new Status(x, b));
                    setStatus.add(new Status(x, b));
                }
            }

            //装满第二个杯子
            if(b != y){
                if(!setStatus.contains(new Status(a, y))) {
                    queue.add(new Status(a, y));
                    setStatus.add(new Status(a, y));
                }
            }

            //如果第一个杯子可以全部倒入第二个杯子
            if(a <= y - b){
                if(!setStatus.contains(new Status(0, a + b))) {
                    queue.add(new Status(0, a + b));
                    setStatus.add(new Status(0, a + b));
                }
            }

            //如果第二个杯子可以全部倒入第一个杯子
            if(x - a >= b){
                if(!setStatus.contains(new Status(a + b, 0))) {
                    queue.add(new Status(a + b, 0));
                    setStatus.add(new Status(a + b, 0));
                }
            }

            //如果第一个杯子可以倒满第二个杯子且有剩余
            if(a > y - b){
                if(!setStatus.contains(new Status(a - (y - b), y))) {
                    queue.add(new Status(a - (y - b), y));
                    setStatus.add(new Status(a - (y - b), y));
                }
            }

            //如果第二个杯子可以倒满第一个杯子且有剩余
            if(x - a < b){
                if(!setStatus.contains(new Status(x, b - (x - a)))) {
                    queue.add(new Status(x, b - (x - a)));
                    setStatus.add(new Status(x, b - (x - a)));
                }
            }

            //倒空第一个杯子
            if(!setStatus.contains(new Status(0, b))) {
                queue.add(new Status(0, b));
                setStatus.add(new Status(0, b));
            }

            //倒空第二个杯子
            if(!setStatus.contains(new Status(a, 0))) {
                queue.add(new Status(a, 0));
                setStatus.add(new Status(a, 0));
            }
        }
        return false;
    }
}

运行的效果很差，今天没有时间继续优化了，不想使用数学方法