1306.jump-game-iii.md

1306. Jump Game III

Traversal

Each i is a node, and the adjacent nodes are i + arr[i] and i - arr[i] (in the boundary), then we can use DFS or BFS to start from start and traverse the graph to find the destination 0.

fun canReach(arr: IntArray, start: Int): Boolean {
    return dfs(arr, start, hashSetOf<Int>())
}

fun bfs(arr: IntArray, start: Int): Boolean {
    val n = arr.size
    val visited = HashSet<Int>()
    val queue = ArrayDeque<Int>()
    queue.addLast(start)
    visited.add(start)
    while (queue.isNotEmpty()) {
        val i = queue.removeFirst()
        if (arr[i] == 0) return true
        val prev = i - arr[i]
        if (prev >= 0 && prev !in visited) {
            queue.addLast(prev)
            visited.add(prev)
        }
        val next = i + arr[i]
        if (next < n && next !in visited) {
            queue.addLast(next)
            visited.add(next)
        }
    }
    return false
}

private fun dfs(arr: IntArray, i: Int, visited: HashSet<Int>): Boolean {
    if (i < 0 || i >= arr.size) return false
    if (i in visited) return false

    if (arr[i] == 0) return true
    visited.add(i)
    return dfs(arr, i - arr[i], visited) || dfs(arr, i + arr[i], visited)
}