这个问题是在之前面试一个公司的时候遇到的，以前没遇到过这种问题，猛然上来有点懵逼。不过几分钟整理思路有了些许解题方案，但临时想的方案漏洞还是有些，思路有了，大方向对了，写代码虽然说就简单了，但大脑混沌状态真的是还不一定写出完美的代码。

题意：

给你两个容器 A B 问是否能够经过有限的步骤倒水,得到容量为 C 的水

输出最小的步数,同时输出每一步的操作。

如果不能达到目标状态,则输出impossible

思路：

总状态只有那么多, 反正每一步后都只有 6 种操作明显的 BFS 关键是每一步路径的记录。

其实就是个A星算法

每层的操作就六种可能：

一：用水池中的水装满 A

二：用水池中的水装满 B

三：把 A 中的水全部倒进废水池

四：把 B 中的水全部倒进废水池

五：把 A 中的水倒进 B 【不能溢出】

那么对应可能会有两种状态：用 k1 表示 A 中的水, k2 表示 B 中的水

如果 k1+k2 <= B 则 k2 = k1+k2; k1 = 0 【不能够装满容器 B】注意顺序

否则 k1 = k1+k2-B; k2 = B 【能够装满容器 B】

六：把 B 中的水倒进 A 【不能溢出】

也有两种情况,分析同上

如果 k1+k2 <= A 则 k1 = k1+k2; k2 = 0;

否则 k2 = k1+k2-A; k1 = A

之前也参考了网上几个代码，写的还是有点混沌，但说实话感觉还是我这个更清晰

/**** @Author: <> * @Description：* 1:->a* 2:->b* 3:a->* 4:b->* 5:a->b* 6:b->a* @Date: Created in : * @Modified by:*/public class CurrStatus {public int ka=0,kb=0;public int op=0;public CurrStatus pre;}

package com.fjsh.mnp;import com.fjsh.mnp.models.CurrStatus;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;/*** @Author: <>* @Description：* @Date: Created in :* @Modified by:*/public class SelfMain {public static void main(String[] args) {final CurrStatus head = new CurrStatus();List<CurrStatus> currStatusList=new LinkedList<CurrStatus>(){{add(head);}};int a = 3, b = 5, c = 4;CurrStatus tail = dealPool(currStatusList, a, b, c);if (tail == null) {System.out.println("impossible");} else {List<Integer> ops=new ArrayList<Integer>();while (tail.op != 0) {ops.add(tail.op);tail = tail.pre;}for(int i=ops.size()-1;i>=0;i--){if(ops.get(i)==1){System.out.println("倒满a");}if(ops.get(i)==2){System.out.println("倒满b");}if(ops.get(i)==3){System.out.println("倒出a");}if(ops.get(i)==4){System.out.println("倒出b");}if(ops.get(i)==5){System.out.println("a倒入b");}if(ops.get(i)==6){System.out.println("b倒入a");}}}}public static CurrStatus dealPool(List<CurrStatus> currStatusList, int a, int b, int pool) {if(a+b<pool){return null;}int max=0;while (max<a*b){List<CurrStatus> currStatuses = new LinkedList<CurrStatus>();for (CurrStatus currStatus : currStatusList) {//循环处理六种条件for (int i = 1; i <= 6; i++) {CurrStatus item = new CurrStatus();item.op = i;item.pre = currStatus;if (i == 1) {item.ka = a;item.kb = currStatus.kb;} else if (i == 2) {item.kb = b;item.ka = currStatus.ka;} else if (i == 3) {item.ka = 0;item.kb = currStatus.kb;} else if (i == 4) {item.kb = 0;item.ka = currStatus.ka;} else if (i == 5) {if (currStatus.ka + currStatus.kb <= b) {item.ka = 0;item.kb = currStatus.ka + currStatus.kb;} else if (currStatus.ka + currStatus.kb > b) {item.kb = b;item.ka = (currStatus.ka + currStatus.kb) - b;}} else if (i == 6) {if (currStatus.ka + currStatus.kb <= a) {item.kb = 0;item.ka = currStatus.ka + currStatus.kb;} else if (currStatus.ka + currStatus.kb > a) {item.ka = a;item.kb = (currStatus.ka + currStatus.kb) - a;}}if (item.ka == pool || item.kb == pool || item.ka+ item.kb == pool) {return item;}currStatuses.add(item);}}max++;currStatusList=currStatuses;}return null;}}

附带上当时参考的url：/A/n2d99RL6dD/

搞点积分不容易，有兴趣的下载下：/download/a925907195/11173095