建设银行遵义分行网站电子商务网站建设与维护期末

有一个水壶容量或者两个水壶加起来总容量为目标容量

总共有八种选择：第一种倒满x,第二种倒满y,第三种清空x,第四种清空y,第五种x 倒给 y y能装满 ，第六种 x 倒给 y x倒完, 。。。。

这里用深度遍历，时间超时

class Solution {public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {//深度递归//用一个visited map来判断 当前情况是否能成功，因此只需要置为false一次即可，不需要反复操作//存储水量，涉及到判断，重写写一个类来存储State state = new State(0, 0);ArrayList<State> states = new ArrayList<>();return dfs(jug1Capacity,jug2Capacity,targetCapacity,state,states);}private boolean dfs(int jug1Capacity, int jug2Capacity, int targetCapacity, State state, List states) {if (states.contains(state))return false;states.add(state);//结束条件if (state.x < 0 || state.y < 0 || state.x > jug1Capacity || state.y > jug2Capacity)return false;if (state.x == targetCapacity || state.y == targetCapacity || state.x + state.y == targetCapacity)return true;//总共有八种情况//第一种倒满x,第二种倒满y,第三种清空x,第四种清空y,第五种x 倒给 y y能装满 ，第六种 x 倒给 y x倒完, 。。。。if (dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(jug1Capacity,state.y),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x, jug2Capacity),states)||dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(0, state.y),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x, 0),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x - (jug2Capacity - state.y), jug2Capacity),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(0, state.y + state.x),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(jug1Capacity, state.y - (jug1Capacity - state.x)),states)|| dfs(jug1Capacity,jug2Capacity,targetCapacity,new State(state.x + state.y, 0),states))return true;return false;}
}class  State{int x;int y;public State(int x, int y) {this.x = x;this.y = y;}@Overridepublic 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;}@Overridepublic int hashCode() {return Objects.hash(x, y);}
}