1654. Minimum Jumps to Reach Home 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> blackSet = new HashSet<>();
        for (int f : forbidden) {
            blackSet.add(f);
        }

        int jumps = 0;
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[6000]; // 0: 未访问，1: 由前进到达，-1: 由后退到达
        queue.offer(0);
        visited[0] = 1;

        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                int position = queue.poll();
                if (position == x) {
                    return jumps;
                }
                int front = position + a;
                int back = position - b;
                if (front < visited.length && !blackSet.contains(front) && visited[front] <= 0) { // 注意此处的小于等于很关键，因为不能连续两次回退的限制，对于同一个位置，如果通过前进到达，能搜索的范围更广
                    queue.offer(front);
                    visited[front] = 1;
                }
                if (visited[position] != -1 && back >= 0 && !blackSet.contains(back) && visited[back] == 0) {
                    queue.offer(back);
                    visited[back] = -1;
                }
            }
            jumps++;
        }

        return -1;
    }
}

References

1654. Minimum Jumps to Reach Home