Show problems as
Classic problem #909MediumArrayBreadth-First SearchMatrix

Snakes and Ladders

Real-world version: Fewest Rolls on the Chute Board
Tracked in this browser only
Read Snakes and Ladders on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A promotional game is played on a square board of n * n tiles, handed to you as the grid board. The tiles are numbered 1 to n * n in a back-and-forth path: numbering starts at the bottom-left cell of the grid and runs left to right along the bottom row, then right to left along the row above it, then left to right again, alternating direction on every row up to the top one.

A cell holds either -1, meaning its tile is ordinary, or the number of another tile, meaning a chute leaves that tile: a counter that lands on it is carried straight to the tile written in the cell. A counter carried by a chute stays put once it arrives, even if the tile it arrives on also has a chute leaving it. Tile 1 and tile n * n are never the start of a chute.

The counter begins on tile 1. One turn means picking a number of tiles to advance, anything from 1 to 6, moving the counter that far along the numbering, and then taking the chute from the tile it landed on if there is one. Advancing past tile n * n is not allowed, so near the end the choice narrows.

Return the fewest turns needed to bring the counter to tile n * n, or -1 if no sequence of turns gets it there.

Examples

Example 1

Input
board = [[-1, -1], [-1, -1]]
Output
1

The tiles run 1, 2 along the bottom row and then 4, 3 along the top row. Advancing three tiles from tile 1 lands on tile 4, which is the last tile, so one turn is enough.

Example 2

Input
board = [[-1, -1, -1], [-1, -1, -1], [-1, -1, 9]]
Output
1

The cell at row 2, column 2 is tile 3, and its chute leads to tile 9. Advancing two tiles from tile 1 lands on tile 3, which carries the counter to tile 9 in the same turn.

Example 3

Input
board = [[2, 2, -1], [2, 2, 2], [-1, -1, 2]]
Output
-1

Every tile from 3 to 8 has a chute back to tile 2, and from tile 2 only tiles 3 to 8 are within reach, so the counter can never arrive at tile 9.

Constraints

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is -1 or a tile number in the range [1, n * n].
  • Neither tile 1 nor tile n * n is the start of a chute.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_rolls(board: list[list[int]]) -> int:
Java
public int fewestRolls(int[][] board)

More on the same topics