909. Snakes and Ladders

解題說明

C++ 解法

複雜度分析

虛擬碼

1. Set n = board size, target = n * n
2. Define getCell(num):
   a. Compute 0-indexed pos = num - 1
   b. rowFromBottom = pos / n, col = pos % n
   c. If rowFromBottom is odd, col = n - 1 - col (reverse direction)
   d. r = n - 1 - rowFromBottom
   e. If board[r][col] != -1, return board[r][col]; else return num
3. Initialize visited[1..n²] = false; mark visited[1] = true
4. Push cell 1 into BFS queue; steps = 0
5. While queue is not empty:
   a. For each cell in current BFS level:
      - Dequeue curr; if curr == target, return steps
      - For dice = 1 to 6:
        * next = curr + dice; if next > target, break
        * next = getCell(next)
        * If not visited[next]: mark visited, enqueue next
   b. Increment steps
6. Return -1 (unreachable)

其他解法

延伸思考