Little fish的难题
Time Limit: 1 Sec Memory Limit: 128 MB
Little fish是一个很聪明很古怪的孩子,他很喜欢在夜深人静的时候飞速的敲代码,但这两天晚上都没听到他发出的噪音,只见他傻傻地坐在那儿,寝室的你很好奇的去问了他原因,原来他被一个问题难住了。这个问题是这样的:有一天他玩弄水杯的时候发现的,他有三个容量分别为整数X,Y,Z(1<=X,Y,Z<=20)的水杯,一开始的时候,X和Y水杯都是空的,只有Z水杯是装满水的。我们可以把一个水杯的水倒到另一个水杯中,直到被倒入的水杯装满或原本的水杯的水全部倒空。
你的任务:写一个程序帮助Little fish找出当X水杯空的时候,Z水杯中水的剩余量的所有可能。

传送门:SHUOJ1867

Input

有多组测试数据,每组测试数据是一行上的三个整数X,Y,Z,(1<=X,Y,Z<=20)。

Output

对于每组测试数据。答案只有一行,列出当X桶是空的时候,Z桶水所剩量的所有可能性,从小到大排列,之间空一格,尾部无多余空格。

Sample Input

1
2
8 9 10
2 5 10

Sample Output

1
2
1 2 8 9 10
5 6 7 8 9 10

题解

好久没写bfs了,反正都是穷举法加记忆数组防止循环 就是代码写得搓了点= =
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.io.*; 
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
public class Main {
static class Bottle{
int x;
int y;
int z;
Bottle(int x,int y,int z){
this.x=x;
this.y=y;
this.z=z;
}
}
static int x,y,z;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
x=sc.nextInt();
y=sc.nextInt();
z=sc.nextInt();
ArrayList<Integer> list=bfs(0,0,z);
TreeSet<Integer>set=new TreeSet<Integer>(); //排序加删重
int j=0;
for(int i:list){
set.add(i);
}
Iterator<Integer> i=set.iterator();
while(i.hasNext()){
int temp=i.next();
if(i.hasNext()==false){
System.out.println(temp);
}
else
System.out.print(temp+" ");
}
}

}
public static ArrayList<Integer> bfs(int a,int b,int c){
LinkedBlockingQueue<Bottle>queue=new LinkedBlockingQueue<Bottle>();
boolean[][][] judge=new boolean[x+1][y+1][z+1]; //记录下每一次到达的状态防止循环
ArrayList<Integer>list=new ArrayList<Integer>();
queue.add(new Bottle(a,b,c));
judge[a][b][c]=true;
while(!queue.isEmpty()){
Bottle temp=queue.poll();
if(temp.x==0){
list.add(temp.z);
}
if(temp.y+temp.x<=y){ //x倒入y分两种情况,下同
if(judge[0][temp.y+temp.x][temp.z]==false){ //未到达这个状态
queue.add(new Bottle(0,temp.y+temp.x,temp.z)); //加入队列
judge[0][temp.y+temp.x][temp.z]=true; //记录到过这个状态
}
}
if(temp.y+temp.x>y){
if(judge[temp.x-(y-temp.y)][y][temp.z]==false){
queue.add(new Bottle(temp.x-(y-temp.y),y,temp.z));
judge[temp.x-(y-temp.y)][y][temp.z]=true;
}
}
if(temp.x+temp.z<=z){ //x倒入z
if(judge[0][temp.y][temp.z+temp.x]==false){
queue.add(new Bottle(0,temp.y,temp.z+temp.x));
judge[0][temp.y][temp.z+temp.x]=true;
}
}
if(temp.x+temp.z>z){
if(judge[temp.x-(z-temp.z)][temp.y][z]==false){
queue.add(new Bottle(temp.x-(z-temp.z),temp.y,z));
judge[temp.x-(z-temp.z)][temp.y][z]=true;
}
}
if(temp.x+temp.y<=x){ //y倒入x
if(judge[temp.x+temp.y][0][temp.z]==false){
queue.add(new Bottle(temp.x+temp.y,0,temp.z));
judge[temp.x+temp.y][0][temp.z]=true;
}
}
if(temp.y+temp.x>x){
if(judge[x][temp.y-(x-temp.x)][temp.z]==false){
queue.add(new Bottle(x,temp.y-(x-temp.x),temp.z));
judge[x][temp.y-(x-temp.x)][temp.z]=true;
}
}
if(temp.x+temp.z<=x){ //z倒入x
if(judge[temp.x+temp.z][temp.y][0]==false){
queue.add(new Bottle(temp.x+temp.z,temp.y,0));
judge[temp.x+temp.z][temp.y][0]=true;
}
}
if(temp.z+temp.x>x){
if(judge[x][temp.y][temp.z-(x-temp.x)]==false){
queue.add(new Bottle(x,temp.y,temp.z-(x-temp.x)));
judge[x][temp.y][temp.z-(x-temp.x)]=true;
}
}
if(temp.z+temp.y<=y){ //z倒入y
if(judge[temp.x][temp.y+temp.z][0]==false){
queue.add(new Bottle(temp.x,temp.y+temp.z,0));
judge[temp.x][temp.y+temp.z][0]=true;
}
}
if(temp.z+temp.y>y){
if(judge[temp.x][y][temp.z-(y-temp.y)]==false){
queue.add(new Bottle(temp.x,y,temp.z-(y-temp.y)));
judge[temp.x][y][temp.z-(y-temp.y)]=true;
}
}
if(temp.z+temp.y<=z){ //y倒入z
if(judge[temp.x][0][temp.y+temp.z]==false){
queue.add(new Bottle(temp.x,0,temp.z+temp.y));
judge[temp.x][0][temp.y+temp.z]=true;
}
}
if(temp.z+temp.y>z){
if(judge[temp.x][temp.y-(z-temp.z)][z]==false){
queue.add(new Bottle(temp.x,temp.y-(z-temp.z),z));
judge[temp.x][temp.y-(z-temp.z)][z]=true;
}
}
}
return list;
}
}