状态图----分酒问题

 有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

//更多的情况，节点不是很明显，多是一种“状态”
//瓶子倒来倒去...状态肯定是有限的

  1 import java.util.*;;
  2 
  3 public class 图的bfs_分酒 {
  4     static Set<Node> set = new HashSet<>();
  5     static int[] v = { 9, 7, 4, 2 };
  6     static Queue<Node> queue = new LinkedList<>();
  7     static Node beginNode = new Node("9,0,0,0", 0);
  8     static Node finalNode;
  9 
 10     public static void main(String[] args) {
 11         Scanner scanner = new Scanner(System.in);
 12         // 接受四个整数
 13         String finalState = "";
 14         finalState += scanner.nextInt() + ",";
 15         finalState += scanner.nextInt() + ",";
 16         finalState += scanner.nextInt() + ",";
 17         finalState += scanner.nextInt();
 18         finalNode = new Node(finalState);
 19         add(queue, beginNode);
 20         int res = bfs();
 21         System.out.println(res);
 22     }
 23 
 24     private static void add(Queue<Node> queue, Node node) {
 25         if (!set.contains(node)) {
 26             set.add(node);
 27             queue.add(node);
 28         }
 29     }
 30 
 31     private static int bfs() {
 32         while (!queue.isEmpty()) {
 33             Node now = queue.poll();// 弹出一个
 34             // 如果和目标吻合，则返回
 35             if (now.equals(finalNode)) {
 36                 return now.depth;
 37             }
 38             // 把neighbors（一步操作得到的下一种状态）加入队列
 39             // 先把每个瓶子里面的量得到
 40             int[] state = now.getState();
 41             // i是往外倒的
 42             for (int i = 0; i < state.length; i++) {
 43                 if (state[i] > 0) {// 有酒,如2 7 0 0
 44                     // j是接收的
 45                     for (int j = 0; j < state.length; j++) {
 46                         if (j == i)
 47                             continue;
 48                         // 把i倒完的条件
 49                         int j_KongJian = v[j] - state[j];
 50                         if (j_KongJian >= state[i]) {
 51                             // 形成新状态
 52                             int temp = state[i];
 53                             state[i] = 0;
 54                             state[j] += temp;
 55                             add(queue, new Node(intArr2String(state), now.depth + 1));
 56                             // 恢复
 57                             state[i] = temp;
 58                             state[j] -= state[i];
 59                         }
 60 
 61                         // 把j倒满，j有空间，且i能倒完
 62                         if (j_KongJian > 0 && state[i] >= j_KongJian) {
 63                             int temp = state[i];
 64                             state[i] -= j_KongJian;
 65                             state[j] += j_KongJian;
 66                             add(queue, new Node(intArr2String(state), now.depth + 1));
 67                             // 恢复
 68                             state[i] = temp;
 69                             state[j] -= j_KongJian;
 70                         }
 71                     }
 72                 }
 73             }
 74         }
 75         return -1;
 76     }
 77 
 78     private static String intArr2String(int[] state) {
 79         StringBuilder sb = new StringBuilder();
 80         for (int i = 0; i < state.length; i++) {
 81             sb.append(state[i]).append(",");
 82         }
 83         return sb.deleteCharAt(sb.length() - 1).toString();
 84     }
 85 
 86     static class Node {
 87         String val;// 9,0,0,0
 88         int depth;// 深度，或者说到达这个状态需要的操作次数
 89 
 90         public Node(String val) {
 91             this.val = val;
 92         }
 93 
 94         public Node(String val, int depth) {
 95             this.val = val;
 96             this.depth = depth;
 97         }
 98 
 99         // 把状态字符串转成四个杯子的存量，方便运算
100         public int[] getState() {
101             String[] arr = val.split(",");
102             int[] res = new int[arr.length];
103             for (int i = 0; i < arr.length; i++) {
104                 res[i] = Integer.parseInt(arr[i]);
105             }
106             return res;
107         }
108 
109         @Override
110         public boolean equals(Object o) {
111             if (this == o)
112                 return true;
113             if (o == null || getClass() != o.getClass())
114                 return false;
115 
116             Node node = (Node) o;
117 
118             return val.equals(node.val);
119         }
120 
121         @Override
122         public int hashCode() {
123             return val.hashCode();
124         }
125     }
126 }