# Average 60ms Java solution, idea sharing purpose. Passed

• ``````public class Solution {
boolean reachable = false;//global variable to stop further action quickly
public  boolean canCross(int[] stones) {
Objects.requireNonNull(stones);
reachable=false;

if(stones.length==1)return true;//one stone means the one to the other side
if(stones.length==2) return (stones[1]==1?true:false);
//these two sets are used to reduce the loops
//only process the one of valid position
Set<Integer> validPositions = new HashSet<>();
//set contains visited situation: startpoint:stepTaken
Set<String> visited = new HashSet<String>();
for(int i:stones){
}
visited.add(0+":"+1);//on position 0, move one step

//starting from position 1, with 1 jump already
dfs(visited,validPositions,1,1,stones[stones.length-1]);
return reachable;
}
private  void dfs(Set<String> visited,Set<Integer> validPositions, int curPosition, int lastJump, int endPosition){
//stop right after reached the last element
if(reachable)return;

if( curPosition+lastJump-1==endPosition
||curPosition+lastJump==endPosition ||curPosition+lastJump+1==endPosition){
reachable = true;
return;
}

//next jump would be lastJump-1, or lastJump or lastJump+1
for(int i=-1;i<2;i++) {
if(!reachable) {
int nextPosition = curPosition + lastJump + i;
//frog must move forward, so jumpUnits==0 is invalid
if ( !visited.contains(nextPosition+":"+(lastJump+i)) && lastJump + i > 0 && validPositions.contains(nextPosition)) {
dfs(visited,validPositions, nextPosition, lastJump + i, endPosition);
}
}
}