GuilinDev
Lc0365
05 August 2008
365. Water and Jug Problem
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
装满任意一个水壶 清空任意一个水壶 从一个水壶向另外一个水壶倒水，直到装满或者倒空
思路 BFS
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
// 特判
if (z == 0) {
return true;
}
if (x + y < z) {
return false;
}
State initState = new State(0, 0);
// 广度优先遍历使用队列
Queue<State> queue = new LinkedList<>();
Set<State> visited = new HashSet<>();
queue.offer(initState);
visited.add(initState);
while (!queue.isEmpty()) {
State head = queue.poll();
int curX = head.getX();
int curY = head.getY();
// curX + curY == z 比较容易忽略
if (curX == z || curY == z || curX + curY == z) {
return true;
}
// 从当前状态获得所有可能的下一步的状态
List<State> nextStates = getNextStates(curX, curY, x, y);
// 打开以便于观察，调试代码
// System.out.println(head + " => " + nextStates);
for (State nextState : nextStates) {
if (!visited.contains(nextState)) {
queue.offer(nextState);
// 添加到队列以后，必须马上设置为已经访问，否则会出现死循环
visited.add(nextState);
}
}
}
return false;
}
private List<State> getNextStates(int curX, int curY, int x, int y) {
// 最多 8 个对象，防止动态数组扩容，不过 Java 默认的初始化容量肯定大于 8 个
List<State> nextStates = new ArrayList<>(8);
// 按理说应该先判断状态是否存在，再生成「状态」对象，这里为了阅读方便，一次生成 8 个对象
// 以下两个状态，对应操作 1
// 外部加水，使得 A 满
State nextState1 = new State(x, curY);
// 外部加水，使得 B 满
State nextState2 = new State(curX, y);
// 以下两个状态，对应操作 2
// 把 A 清空
State nextState3 = new State(0, curY);
// 把 B 清空
State nextState4 = new State(curX, 0);
// 以下四个状态，对应操作 3
// 从 A 到 B，使得 B 满，A 还有剩
State nextState5 = new State(curX - (y - curY), y);
// 从 A 到 B，此时 A 的水太少，A 倒尽，B 没有满
State nextState6 = new State(0, curX + curY);
// 从 B 到 A，使得 A 满，B 还有剩余
State nextState7 = new State(x, curY - (x - curX));
// 从 B 到 A，此时 B 的水太少，B 倒尽，A 没有满
State nextState8 = new State(curX + curY, 0);
// 没有满的时候，才需要加水
if (curX < x) {
nextStates.add(nextState1);
}
if (curY < y) {
nextStates.add(nextState2);
}
// 有水的时候，才需要倒掉
if (curX > 0) {
nextStates.add(nextState3);
}
if (curY > 0) {
nextStates.add(nextState4);
}
// 有剩余才倒
if (curX - (y - curY) > 0) {
nextStates.add(nextState5);
}
if (curY - (x - curX) > 0) {
nextStates.add(nextState7);
}
// 倒过去倒不满才倒
if (curX + curY < y) {
nextStates.add(nextState6);
}
if (curX + curY < x) {
nextStates.add(nextState8);
}
return nextStates;
}
private class State {
private int x;
private int y;
public State(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public String toString() {
return "State{" +
"x=" + x +
", y=" + y +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
State state = (State) o;
return x == state.x &&
y == state.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int x = 3;
int y = 5;
int z = 4;
// int x = 2;
// int y = 6;
// int z = 5;
// int x = 1;
// int y = 2;
// int z = 3;
boolean result = solution.canMeasureWater(x, y, z);
System.out.println(result);
}
}