class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        current = 1
        short_cut = {}
        for k in range(n):
            x = (n - 1) - k
            if k % 2 == 0:
                for y in range(n):
                    p = board[x][y]
                    if p != -1:
                        short_cut[current] = p
                    current += 1
            else:
                for y in range(n - 1, -1, -1):
                    p = board[x][y]
                    if p != -1:
                        short_cut[current] = p
                    current += 1
        
        dp = [-1] * (n ** 2 + 1)
        dp[n ** 2] = 0
        def dfs(cur, prev):
            if cur in short_cut:
                prev = cur
                cur = short_cut[cur]
            if cur >= n ** 2:
                return 0
            if dp[cur] != -1:
                return dp[cur]
            res = 10**9
            for i in range(1, 7):
                if cur + i != prev:
                    temp = dfs(cur + i, cur)
                    if temp != -1:
                        res = min(res, temp)
            if res == 10**9: 
                dp[cur] = -1
            else: 
                dp[cur] = res + 1
            return dp[cur]
        dfs(1, 0)

        # print(short_cut)
        # print(dp)
        return dp[1]   

class Solution:
    def snakesAndLadders(self, board):
        arr, nn, q, seen, moves = [0], len(board) ** 2, [1], set(), 0
        for i, row in enumerate(board[::-1]): arr += row[::-1] if i % 2 else row
        while q:
            new = []
            for sq in q:
                if sq == nn: return moves 
                for i in range(1, 7):
                    if sq + i <= nn and sq + i not in seen:
                        seen.add(sq + i)
                        new.append(sq + i if arr[sq + i] == -1 else arr[sq + i])
            q, moves = new, moves + 1
        return -1