Java BFS solution


  • 0
    D
    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) {
                position.add(stone);
            }
            Queue<Tuple> queue = new LinkedList<>();
            Set<Tuple> tuples = new HashSet<>();
            Tuple first = new Tuple(1, 1);
            queue.offer(first);
            tuples.add(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);
                            tuples.add(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;
            }
        }
    }
    

Log in to reply
 

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