蓝桥-分酒问题

Dear 丶 2022-04-12 14:15 180阅读 0赞

3. 分酒问题  
有4个红酒瓶子，它们的容量分别是：9升, 7升, 4升, 2升  
开始的状态是 \[9,0,0,0\]，也就是说：第一个瓶子满着，其它的都空着。

允许把酒从一个瓶子倒入另一个瓶子，但只能把一个瓶子倒满或把一个瓶子倒空，不能有中间状态。  
这样的一次倒酒动作称为1次操作。

假设瓶子的容量和初始状态不变，对于给定的目标状态，至少需要多少次操作才能实现？  
本题就是要求你编程实现最小操作次数的计算。

输入：最终状态（空格分隔）  
输出：最小操作次数（如无法实现，则输出-1）

例如：  
输入：  
9 0 0 0  
应该输出：  
0

输入：  
6 0 0 3  
应该输出：  
\-1

输入：  
7 2 0 0  
应该输出：  
2

测试用例：  
输入：2,4,1,2  
输出：6  
输入：3,1,3,2  
输出：9  
输入：2,6,1,0  
输出：7

// 图的节点就是状态，在运行中才产生
    import java.util.*;
    public class A
    {
      // 当前状态的可达集合
      static Set move(String cur){
        int[] cap = {9,7,4,2};
        int[] data = new int[4];
        String[] ss = cur.split(" ");
        for(int i=0; i<4; i++) data[i] = Integer.parseInt(ss[i]);
        
        Set set = new HashSet();
        // 试着从i倒入j
        for(int i=0; i<4; i++)
        for(int j=0; j<4; j++){
          if(j==i) continue;
          if(data[i]==0) continue;  //源空
          if(data[j]==cap[j]) continue; //目标满了
          
          int sum = data[i]+data[j];  
          int vi = (sum <= cap[j])? 0 : sum - cap[j]; // 假如倒酒后，i号的新值
          int vj = (sum <= cap[j])? sum : cap[j];  // 假如倒酒后，j号的新值
      
          //生成新的状态串
          String s = "";
          for(int k=0; k<4; k++){
            if(k==i) s += vi + " ";
            else if(k==j) s += vj + " ";
            else s += data[k] + " ";
          }
          
          set.add(s.trim());
        }
        
        return set;
      }
    
      static int f(Set hist, Set from, String goal){
        if(from.contains(goal)) return 0;
        
        Set from2 = new HashSet();
        for(Object it: from){
          Set t = move(it.toString());
          from2.addAll(t);
        }
        
        from2.removeAll(hist);
        if(from2.isEmpty()) return -1;
        
        hist.addAll(from2);
        int r = f(hist, from2, goal);
        if(r<0) return r;
        return r + 1;
      }
    
      public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        Set from = new HashSet(); //出发态
        from.add("9 0 0 0");
        Set hist = new HashSet(); //所有历史态
        hist.addAll(from);
        
        System.out.println(f(hist,from,scan.nextLine().trim()));
      }
    }