有一個水壺容量或者兩個水壺加起來總?cè)萘繛槟繕?biāo)容量

總共有八種選擇：第一種倒?jié)Mx,第二種倒?jié)My,第三種清空x,第四種清空y,第五種x 倒給 y y能裝滿 ，第六種 x 倒給 y x倒完, 。。。。

這里用深度遍歷，時間超時

class Solution {public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {//深度遞歸//用一個visited map來判斷 當(dāng)前情況是否能成功，因此只需要置為false一次即可，不需要反復(fù)操作//存儲水量，涉及到判斷，重寫寫一個類來存儲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);//結(jié)束條件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;//總共有八種情況//第一種倒?jié)Mx,第二種倒?jié)My,第三種清空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);}
}