倒水問題
/** * Created by oy on 2017/2/4. */public class Main { //需要的水體積 PRivate int find; //各個容器的容量 private int[] capacity; //中杯和小杯的剩余量 private boolean[][] vis; //是否找到 private boolean isHaveAns; //隊列 Node[] queue = new Node[100]; int begin = 0; int tail = 1;// Queue<Node> queue = new PriorityQueue<>(); public static void main(String[] args){ Main main = new Main(); main.vis = new boolean[6][6]; main.find = 4; main.capacity = new int[3]; main.capacity[0] = 6; main.capacity[1] = 3; main.capacity[2] = 1; main.bfs(); } private void bfs(){ Node node = new Node(); node.cup[0] = capacity[0]; vis[0][0] = true; queue[begin] = node; while(begin<tail) { changeWater(queue[begin++]); } if(!isHaveAns){ System.out.println("找不到方案"); } } private void changeWater(Node node){ int[] cup = node.cup; for(int i = 0; i< cup.length; i++){ for(int j = 0; j< cup.length; j++) { if(i!=j) if(fill(node,i,j)) return; } } } private boolean fill(Node node,int from,int to){ Node clone = node.clone(); int[] cup = clone.cup; if(cup[from] == 0||cup[to] == capacity[to]){ return false; } //倒水 int a = cup[from]; int b = cup[to]; int result = a + b; if(result>capacity[to]){ cup[from] = result - capacity[to]; cup[to] = capacity[to]; }else{ cup[from] = 0; cup[to] = result; } //找到了方案 if(clone.isFound()){ System.out.println("Find a condition"); clone.pre = node; for(Node n = clone;n!= null;n = n.pre){ for (int i : n.cup) System.out.print(i + " "); System.out.println(); } isHaveAns = true; return true; } //添加節點到隊列里面去 if (!vis[clone.cup[1]][clone.cup[2]]) { vis[clone.cup[1]][clone.cup[2]] = true; clone.pre = node; queue[tail++]=clone; } return false; } class Node{ Node pre = null; int[] cup = new int[3]; int depth; public boolean isFound(){ for(int i = 0;i<3;i++){ if(cup[i] == find){ return true; } } return false; } @Override public Node clone(){ Node node = new Node(); node.cup = cup.clone(); node.depth = depth; return node; } }}新聞熱點
疑難解答
