不进行状态压缩实现水桶问题的疑问

Question

老师你好，关于水桶智力题，我在思考不使用状态压缩是否可以实现。我是这么做的：构建一个名为Pair的类来保存每个桶有几升水的信息。在具体实现中，我创造一个名叫“visited”的HashMap<Pair, Integer>来记录每个状态是否被访问过：key保存访问到的两个桶的状态，value保存步数。但具体实现中，如果下一个状态"next"是一个自己构建的Pair类，则if（!visited.containsKey(next)）并不能按照所想的执行。就算下一个状态已经被访问过，这个if语句也会判断没被访问。

请问波波老师这什么原因以及如何解决？感谢！

下面是我的猜想：我的Java基本功不是很扎实，我感觉是Java containsKey()方法是在做==比较而不是.equals()的对象比较。所以我可能需要override一个equals方法。

下面是部分代码，如果需要会放更多 (next_state()是自己包装的方法用来输出下一个可能的state)：
public class WaterPuzzle {

private HashMap<Pair, Integer> visited;
private Pair start;
private int fullx;
private int fully;
private int target;

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

    private int getA(){
        return a;
    }

    private int getB(){
        return b;
    }

    private void setA(int newa){
        a = newa;
    }

    private void setB(int newb){
        b = newb;
    }
}

public int minimumStep(int fullx, int fully, int target){

    visited = new HashMap<>();
    this.fullx = fullx;
    this.fully = fully;
    this.target = target;
    start = new Pair(0, 0);

    Queue<Pair> queue = new LinkedList<>();
    queue.add(start);
    visited.put(start, 0);

    while(!queue.isEmpty()){
        Pair out = queue.remove();
        ArrayList<Pair> nexts = next_states(out);
        for(Pair next: nexts){
            if(!visited.containsKey(next)){
                if(out.getA() == next.getA() && out.getB() == next.getB()){ //这步会被执行，与if冲突
                    System.out.println("we are here");
                    return -1;
                }

Answer 1

liuyubobobo 2020-05-20 14:34:18

我没有具体看你的代码，但看你的描述，你的思路是没有问题的。不过如果你使用 HashMap 的话，其中的键的类型，也就是你自定义的 Pair 类，必须覆盖 hashCode 方法，才能被 HashMap 正确调用。哈希表内部需要使用哈希值：）

但本质上，如果你定义了一个哈希值，也是在做状态压缩了，只不过这个状态压缩隐藏在了 Pair 内部。

另外一个方法是使用 TreeMap，这样一来，你的 Pair 仅仅需要实现 Comparable 接口就可以了。在 compareTo 判等的过程中，可以不做状态压缩：）

继续加油！：）

• 提问者 软件工程小白菜 #1

  非常感谢！我尝试下覆盖hashcode方法

• 提问者 软件工程小白菜 #2

  感谢波波老师指导，除了hashcode的问题外，我还debug了一些指针指向的问题，发现在解题中弄清楚哪个变量指向哪个内存是非常重要的。目前我应该已经正确实现出来了。对于x=5, y=3, target=4，我得到的最小步数为6，路径为(0, 0)，(5, 0)，(2, 3)，(2, 0)，(0, 2)，(5, 2)，(4, 3)。并且对于大于10的数字也可以实现，比如x=15, y=11, target=12，最小步数为10，得到的路径为：(0, 0)，(15, 0)，(4, 11)，(4, 0)，(0, 4)，(15, 4)，(8, 11)，(8, 0)，(0, 8)，(15, 8)，(12, 11)。

• liuyubobobo 回复 提问者 软件工程小白菜 #3

  大赞！继续加油！：）