909.md

909. Snakes and Ladders

Solution 1 (time O(n^2), space O(n^2))

class Solution(object):
    def snakesAndLadders(self, board):
        """
        :type board: List[List[int]]
        :rtype: int
        """
        n = len(board)

        def id2rc(cur_id):
            cur_r = (cur_id - 1) / n
            cur_c = (cur_id - 1) % n
            if cur_r % 2 == 1:
                cur_c = n - 1 - cur_c
            cur_r = n - 1 - cur_r
            return cur_r, cur_c

        q = [(1, 0)]
        vis = [False for _ in range(n * n + 1)]
        vis[1] = True
        while q:
            cur_state, cur_level = q.pop(0)
            for i in range(1, 7):
                new_state = cur_state + i
                new_r, new_c = id2rc(new_state)
                if board[new_r][new_c] != -1:
                    new_state = board[new_r][new_c]
                if new_state == n * n:
                    return cur_level + 1
                if not vis[new_state]:
                    vis[new_state] = True
                    q.append((new_state, cur_level + 1))
        return -1