LeetCode Entry
909. Snakes and Ladders
fun snakesAndLadders(board: Array
909. Snakes and Ladders medium
https://t.me/leetcode_daily_unstoppable/96
fun snakesAndLadders(board: Array<IntArray>): Int {
fun col(pos: Int): Int {
return if (((pos/board.size) % 2) == 0)
(pos % board.size)
else
(board.lastIndex - (pos % board.size))
}
val last = board.size * board.size
var steps = 0
val visited = mutableSetOf<Int>()
with(ArrayDeque<Int>().apply { add(1) }) {
while (isNotEmpty() && steps <= last) {
repeat(size) {
var curr = poll()
val jump = board[board.lastIndex - (curr-1)/board.size][col(curr-1)]
if (jump != -1) curr = jump
if (curr == last) return steps
for (i in 1..6)
if (visited.add(curr + i) && curr + i <= last) add(curr + i)
}
steps++
}
}
return -1
}
In each step, we can choose the best outcome, so we need to travel all of them in the parallel and calculate steps number. This is a BFS.
We can avoid that strange order by iterating it and store into the linear array. Or just invent a formula for row and column by given index.
Space: O(n^2), Time: O(n^2), n is a grid size