# Java BFS solution

• ``````public class Solution {
public boolean canCross(int[] stones) {
if (stones == null || stones.length == 0) {
return true;
}
if (stones.length == 1) {
return stones[0] == 0;
}
if (stones.length == 2) {
return stones[0] == 0 && stones[1] == 1;
}
if (stones[0] != 0 || stones[1] != 1) {
return false;
}
Set<Integer> position = new HashSet<>();
for (int stone : stones) {
}
Set<Tuple> tuples = new HashSet<>();
Tuple first = new Tuple(1, 1);
queue.offer(first);
int target = stones[stones.length - 1];
while (!queue.isEmpty()) {
Tuple tuple0 = queue.poll();
if (tuple0.curPos == target) {
return true;
}
if (tuple0.curPos > target) {
continue;
}
for (int step = -1; step <= 1; step++) {
int next = tuple0.curPos + tuple0.lastStep + step;
if (position.contains(next) && next != tuple0.curPos) {
Tuple tuple1 = new Tuple(next, tuple0.lastStep + step);
if (!tuples.contains(tuple1)) {
queue.offer(tuple1);
}
}
}
}
return false;
}

class Tuple {
int curPos;
int lastStep;
public Tuple(int curPos, int lastStep) {
this.curPos = curPos;
this.lastStep = lastStep;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Tuple)) {
return false;
}
Tuple other = (Tuple)obj;
return curPos == other.curPos && lastStep == other.lastStep;
}
@Override
public int hashCode() {
int hash = 17;
hash = hash * 31 + curPos;
hash = hash * 31 + lastStep;
return hash;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.