909. Snakes and Ladders

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        """ tc O(N*N) sc O(N*N)
        """
        r = c = len(board)
        q = collections.deque()
        seen = set()
        q.append(1) # x,y,val
        moves = 1
        while q:
            size = len(q)
            for _ in range(size):
                cur = q.popleft()
                for di in range(1,7):
                    nxt = cur + di 
                    i,j = self.get_pos(nxt,r)
                    if board[i][j] != -1:
                        nxt = board[i][j]

                    if nxt == r*r :
                        return moves
                    
                    if nxt not in seen: 
                        q.append(nxt)
                        seen.add(nxt)
            moves += 1 
        
        return -1 
    def get_pos(self,val,n):
        row = (val-1)//n 
        col = (val-1)%n
        x = n-1-row 
        y = col if row%2 ==0 else n-1-col
        return x,y 

class Solution:
    def snakesAndLadders(self, board):
        n = len(board)
        d = {1: 0}
        bfs = [1]
        for x in bfs:
            snake_ladder = False
            for i in range(min(n*n, x + 6), x, -1):
                a, b = (i - 1) // n, (i - 1) % n
                nxt = board[~a][b if a % 2 == 0 else ~b]
                if nxt > 0: i = nxt
                if i == n * n: return d[x] + 1
                if nxt == -1 and snake_ladder: continue
                if nxt == -1: snake_ladder = True
                if i not in d:
                    d[i] = d[x] + 1
                    bfs.append(i)
        return -1