1654. 到家的最少跳跃次数 - Kotlin 广度优先搜索

Problem: 1654. 到家的最少跳跃次数

思路

跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

这句话指明了本道题中位置的下边界为0，但是没有上边界。由于跳蚤可以无限次地向前跳跃，如果我们不去人为找到一个上边界，在遇到无法达到x的情况时遍历会陷入不断试图向前跳跃的死循环。其他题解中已经证明当position>6000时遍历不再有意义，即一个隐含的上边界6000，这里不再证明。

我们知道，基于广度优先搜索，并记录步数/层数，从起点开始第一次搜索到任意一个点时的当前步数都是起点到该点的最短路径，一个简单的思路是从起点开始BFS，当首次搜索到x时输出当前步数即可

由于只有在首次搜索到点时，当前步数才是到达该点的最少步数，因此应当每次试图在队列中加入状态时，用一个skip结构维护当前已被搜索到的点，当skip中包含该状态时则不加入队列中

由于当前状态是由前一个状态前跳得到时，可以前跳/后跳，而当前状态是由前一个状态后跳得到时，只能进行前跳，因此在搜索路径时，每个状态除了要记录当前的位置以外，还需要记录当前的方向

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution 
const val FORWARD = 0
const val BACK = 1
const val MIN_POS = 0
const val MAX_POS = 6000
fun Solution.minimumJumps(forbidden: IntArray, a: Int, b: Int, x: Int): Int {
    val bfs = ArrayDeque<Pair<Int, Int>>()
    val skip = HashSet<Pair<Int, Int>>()

    forbidden.forEach { skip.add(FORWARD to it);skip.add(BACK to it) }
    bfs.addLast(FORWARD to 0)

    var step = 0
    while (bfs.isNotEmpty()) {
        var cnt = bfs.size
        while (cnt-- > 0) {
            val pair = bfs.removeFirst()
            val direction = pair.first
            val position = pair.second
            if (position == x) {
                return step
            }
            if (position + a <= MAX_POS && !skip.contains(FORWARD to position + a)) {
                skip.add(FORWARD to position + a)
                bfs.addLast(FORWARD to position + a)
            }
            if (position - b >= MIN_POS && !skip.contains(BACK to position - b) && direction != BACK) {
                skip.add(BACK to position - b)
                bfs.addLast(BACK to position - b)
            }
        }
        step++
    }
    return -1
}