题目描述
农夫约翰有三个容量分别为 A,B,C升的挤奶桶。
最开始桶 A和桶 B都是空的,而桶C里装满了牛奶。有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。
请你编写一个程序判断,当A桶是空的时候,C桶中可能包含多少升牛奶,找出所有的可能情况。
输入格式共一行,包含三个整数 A,B,C。
输出格式
共一行,包含若干个整数,表示C桶中牛奶存量的所有可能情况,请将这些数字按升序排列。
数据范围
1≤A,B,C≤20
算法1
bfs $O(n^3)$
时间复杂度 最多搜索$21*21*21*6$条边 而且有重复
java 代码
import java.util.*;
public class Main {
static class Point {//每一个点就是一个状态 最后要求的是(0,y,z)的所有z的情况
int x,y,z;
public Point(int x,int y,int z) {
this.x = x;
this.y = y;
this.z = z;
}
}
static int A,B,C;
static final int N = 21,M = N * N * N;//最多M种状态
static Point[] q = new Point[M];//类似一个储存未倒过牛奶的状态还未变过的点
static boolean[][][] st = new boolean[N][N][N];//保存每种状态是否出现过
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
A = in.nextInt();
B = in.nextInt();
C = in.nextInt();
bfs();
for(int c = 0; c <= C; c++) {//先从小到大枚举c桶即可从小到大输出c了
for(int b = 0; b <= B; b++) {
if(st[0][b][c]) System.out.print(c + " ");
}
}
}
public static void bfs() {
int hh = 0,tt = 0;//定义队头队尾
q[0] = new Point(0,0,C);//初始化 入队
st[0][0][C] = true;//初始化
while(hh <= tt) {//如果发现已经不能再有新的状态的点了说明要退出了 即所有点都成环了
Point p = q[hh++];//取出队头
int[] W = new int[]{A,B,C};//定义最大容量
for(int i = 0; i <= 2; i++)//从第i个桶倒到第j个桶
for(int j = 0; j <= 2; j++) {
if(i != j) {//不能自己倒自己
int[] w = new int[]{p.x,p.y,p.z};//存储当前点的状态 即A,B,C桶牛奶各有多少
int cur = Math.min(w[i],W[j]-w[j]);//看能倒多少
w[i] -= cur;//i桶减少cur牛奶
w[j] += cur;//j桶增加cur牛奶
int a = w[0],b = w[1],c = w[2];
if(!st[a][b][c]) {//看这种状态之前出现过了吗
st[a][b][c] = true;//没有就加上这种新状态
q[++tt] = new Point(a,b,c);//并且入队 继续bfs看能不能找到新的状态
}
}
}
}
}
}