leetcode snake and ladders - kotlin

 

 

https://leetcode.com/problems/snakes-and-ladders

Snakes and Ladders - LeetCode

class Solution {

    fun snakesAndLadders(board: Array<IntArray>): Int {
        val iq = mutableListOf<Pair<Int, Int>>(Pair(1, 0))
        val lst = board.size * board.size
        val visit = BooleanArray(400 + 1){false}
        val accs = Array<IntArray>(401){IntArray(401){Int.MAX_VALUE}}

            while(iq.isNotEmpty()){
                val (t, acc) = iq.first()
                iq.removeAt(0)

                val range = getPossibleMovePoints(board = board, curr = t)
                
                for(num in range){
                    var next = num
                    val (r, c) = getAxisFromPoint(curr = next, n = board.size)
                    if(num > lst) return -1
                    if(board[r][c] != -1)  next = board[r][c]
                    if(next == lst) return acc + 1
                    if(!visit[next]) {
                        visit[next] = true
                        iq.add(Pair(next, acc + 1))
                    }
                }
            }
            return -1
    }

    // generate the range of possible move point 
    fun getPossibleMovePoints(board: Array<IntArray>, curr: Int): IntRange  {
        return (curr + 1)..Math.min(curr + 6, board.size * board.size)
    }

    // get Axis from current point
    // input currentPoint
    // out: Pair of axis
    fun getAxisFromPoint(curr: Int, n: Int): Pair<Int, Int> {
        val r = (n-1) - (curr-1) / n
        val c = if(((n-1 - r) % 2) == 0) (curr-1) % n else (n-1) - ((curr - 1) % n)
        return Pair(r, c)
    }
}

BFS 이용

시간 엄청 많이 걸림...