## 題解

### BFS solution

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)

        def rcToIdx(x,y):
            res = (n ** 2) - (y * n)
            if y % 2 == 1:
                res -= n - 1 - x
            else:
                res += x
            return res
        
        def idxToRc(idx): # 轉換成 row col 索引
            r, c = (idx - 1) // n, (idx - 1) % n
            if r % 2 == 1:
                c = n - 1 - c
            return c,n - 1 - r
        
        queue = [(1,0)] # 從 1 開始走
        visited = set() # 紀錄是否已經訪問過

        while queue:
            node, steps = queue.pop(0)
            for next_step in range(node + 1 , min(node + 6, n ** 2) + 1):
                x,y = idxToRc(next_step)
                if board[y][x] > 0: # 如果可以跳
                    next_step = board[y][x]
                if next_step == n ** 2: # 如果到達 n ** 2
                    return steps + 1
                if next_step not in visited: # 如果還沒走訪過
                    visited.add(next_step)
                    queue.append((next_step,steps + 1))

        return -1