java 解法, 执行用时: 33 ms, 内存消耗: 42.9 MB, 提交时间: 2023-08-30 09:56:31

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> s = new HashSet<>();
        for (int v : forbidden) {
            s.add(v);
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {0, 1});
        final int n = 6000;
        boolean[][] vis = new boolean[n][2];
        vis[0][1] = true;
        for (int ans = 0; !q.isEmpty(); ++ans) {
            for (int t = q.size(); t > 0; --t) {
                var p = q.poll();
                int i = p[0], k = p[1];
                if (i == x) {
                    return ans;
                }
                List<int[]> nxt = new ArrayList<>();
                nxt.add(new int[] {i + a, 1});
                if ((k & 1) == 1) {
                    nxt.add(new int[] {i - b, 0});
                }
                for (var e : nxt) {
                    int j = e[0];
                    k = e[1];
                    if (j >= 0 && j < n && !s.contains(j) && !vis[j][k]) {
                        q.offer(new int[] {j, k});
                        vis[j][k] = true;
                    }
                }
            }
        }
        return -1;
    }
}

golang 解法, 执行用时: 12 ms, 内存消耗: 7 MB, 提交时间: 2023-08-30 09:55:52

func minimumJumps(forbidden []int, a int, b int, x int) (ans int) {
	s := map[int]bool{}
	for _, v := range forbidden {
		s[v] = true
	}
	q := [][2]int{[2]int{0, 1}}
	const n = 6000
	vis := make([][2]bool, n)
	vis[0][1] = true
	for ; len(q) > 0; ans++ {
		for t := len(q); t > 0; t-- {
			p := q[0]
			q = q[1:]
			i, k := p[0], p[1]
			if i == x {
				return
			}
			nxt := [][2]int{[2]int{i + a, 1}}
			if k&1 == 1 {
				nxt = append(nxt, [2]int{i - b, 0})
			}
			for _, e := range nxt {
				j, l := e[0], e[1]
				if j >= 0 && j < n && !s[j] && !vis[j][l] {
					q = append(q, [2]int{j, l})
					vis[j][l] = true
				}
			}
		}
	}
	return -1
}

golang 解法, 执行用时: 16 ms, 内存消耗: 6.7 MB, 提交时间: 2023-08-30 09:55:05

// dfs
func minimumJumps(forbidden []int, a int, b int, x int) int {
    lower := 0
    maxVal := 0
    for _, val := range forbidden {
        maxVal = max(maxVal, val);
    }
    upper := max(maxVal + a, x) + b
    q := [][3]int{[3]int{0, 1, 0}}
    visited := make(map[int]bool)
    forbiddenSet := make(map[int]bool)
    visited[0] = true
    
    for _, position := range(forbidden) {
        forbiddenSet[position] = true
    }
    for len(q) > 0 {
        position, direction, step := q[0][0], q[0][1], q[0][2]
        q = q[1:]
        if position == x {
            return step
        }
        nextPosition, nextDirection := position + a, 1
        _, ok1 := visited[nextPosition * nextDirection]
        _, ok2 := forbiddenSet[nextPosition]
        if lower <= nextPosition && nextPosition <= upper && !ok1 && !ok2 {
            visited[nextPosition * nextDirection] = true
            q = append(q, [3]int{nextPosition, nextDirection, step + 1})
        }
        if direction == 1 {
            nextPosition, nextDirection := position - b, -1
            _, ok1 := visited[nextPosition * nextDirection]
            _, ok2 := forbiddenSet[nextPosition]
            if lower <= nextPosition && nextPosition <= upper && !ok1 && !ok2 {
                visited[nextPosition * nextDirection] = true
                q = append(q, [3]int{nextPosition, nextDirection, step + 1})
            }
        }
    }
    return -1
}

func max(x int, y int) int {
    if x < y {
        return y
    }
    return x
}

python3 解法, 执行用时: 100 ms, 内存消耗: 15.9 MB, 提交时间: 2022-08-01 11:07:23

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        forbidden = set(forbidden)
        Q = deque()
        Q.append((0, 0, False))
        while Q:
            cur, cnt, used = Q.popleft()
            if cur == x:
                # 第一次到x即最小步数，因为队列后序元素cnt都是大于等于当前cnt的
                return cnt
            if cur + a < 6000 and cur + a not in forbidden:
                # 6000是往右探索的最大值，x最大为2000
                forbidden.add(cur+a)
                Q.append((cur+a, cnt+1, False))
            if not used and cur - b > 0 and cur - b not in forbidden:
                # forbidden.add(cur-b) 
                # 这里不能forbidden，因为后退回cur-b处时，无法覆盖前进到cur-b再后退到cur-2b的情况。
                Q.append((cur-b, cnt+1, True))
        return -1

python3 解法, 执行用时: 104 ms, 内存消耗: 22.4 MB, 提交时间: 2022-08-01 11:07:03

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        forbidden = set(forbidden)
        self.key = -1
        
        def dfs(num, cnt, back):
            if self.key < 0 and 0 <= num <= 6000:  # # 6000是往右探索的最大值，x最大为2000
                if num == x:  # 第一次遍历到 x时的次数即为结果，暂存结果，不再递归
                    self.key = cnt  
                    return
                if num+a not in forbidden:
                    forbidden.add(num+a)  # 防止无限递归，比如 a = b 时，不加限制，就会出现无限递归
                    dfs(num+a, cnt+1, 0)
                if num-b not in forbidden and back != 1:  # 若back为1说明上次就是往后跳的
                    dfs(num-b, cnt+1, 1)
                
        dfs(0, 0, 0)
        return self.key