有兩個杯子，一個杯子容量為3，另一個容量為5.? 怎么倒水才能得到體積為4的水.

可以給一個杯子加滿水、或倒光、或把一個杯子的水加到另一個杯子中.

1 import java.util.ArrayList; 2 import java.util.Collections; 3 import java.util.LinkedList; 4 import java.util.Queue; 5 6 import static java.lang.Integer.min; 7 8 public class WaterPuzzle { 9 10 private int[] pre; 11 private int end; 12 13 public WaterPuzzle() { 14 boolean[] visited = new boolean[100]; 15 pre = new int[100]; 16 end = -1; 17 // BFS 18 Queue<Integer> queue = new LinkedList<>(); 19 queue.add(0); 20 visited[0] = true; 21 while (!queue.isEmpty()) { 22 int cur = queue.remove(); 23 int a = cur / 10; 24 int b = cur % 10; 25 26 ArrayList<Integer> nexts = new ArrayList<>(); 27 nexts.add(5 * 10 + b); 28 nexts.add(a * 10 + 3); 29 nexts.add(a * 10 + 0); 30 nexts.add(0 * 10 + b); 31 32 int IN = min(3 - b, a); 33 nexts.add((a - IN) * 10 + b + IN); 34 IN = min(5 - a, b); 35 nexts.add((a + IN) * 10 + b - IN); 36 37 for (int next : nexts) { 38 if (!visited[next]) { 39 visited[next] = true; 40 queue.add(next); 41 pre[next] = cur; 42 if (next / 10 == 4 || next % 10 == 4) { 43 end = next; 44 return; 45 } 46 } 47 } 48 } 49 } 50 51 public Iterable<Integer> result() { 52 ArrayList<Integer> ans = new ArrayList<>(); 53 if (end == -1) 54 return ans; 55 int p = end; 56 while (p != 0) { 57 ans.add(p); 58 p = pre[p]; 59 } 60 ans.add(0); 61 Collections.reverse(ans); 62 return ans; 63 } 64 65 public static void main(String[] args) { 66 System.out.println(new WaterPuzzle().result()); 67 } 68 }

?

轉載于:https://www.cnblogs.com/AntonLiu/p/11391973.html

總結

以上是生活随笔為你收集整理的倒水问题(Java)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。