1654.Minimum_Jumps_to_Reach_Home.md

1654. Minimum Jumps to Reach Home

這題很類似 [752. Open the Lock] 同樣是需要使用 Breadth-First Search 來解決:

1. 首先要把 forbidden 轉換成一個 set 來加速查找
   • 假如起點是 forbidden 的話就直接回傳 -1
2. 使用 Breadth-First Search 來找出最短的路徑
   • 這裡需要使用一些資料結構來記錄上一次使用的是 forward, backward
   • 在紀錄 visited 的時候要注意，在這題因為前後 Jump 的限制，上一次是 backward 即使與 forward 重複但也可能會導致不同的分支
     • 在 visited 中可以只添加對 forward 的限制

Solution:

func minimumJumps(forbidden []int, a int, b int, x int) int {
    if x == 0 {
        return 0
    }
    // Step 1: Set forbidden for a set to quick search.
    lock := map[int]bool{}
    for _, d := range forbidden {
        lock[d] = true
    }

    // If start point is forbidden return -1
    if lock[0] {
        return -1
    }

    // Step 2: Breadth-First Search.
    res := 0
    queue := []int{0}
    visited := map[int]int{queue[0]: a}
    for len(queue) > 0 {
        size := len(queue)
        for _, s := range queue {
            if s == x {
                return res
            }
            forward, backward := s+a, s-b
            if v, exist := visited[forward]; (!exist || v==b) && forward <= 5000+x && !lock[forward] {
                queue = append(queue, forward)
                visited[forward] = a
            }
            // If last time jump is backward pass.
            if visited[s] == b {
                continue
            }
            // The numbers passed backward can be repeated.
            if _, exist := visited[backward]; !exist && backward > 0 && !lock[backward] {
                queue = append(queue, backward)
                visited[backward] = b
            }
        }
        queue = queue[size:]
        res++
    }
    return -1
}