0534MediumArrayBreadth-First SearchMatrix

Fewest Rolls on the Chute Board

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def fewest_rolls(board: list[list[int]]) -> int:

Java

public int fewestRolls(int[][] board)

The intended approach

Time O(n^2): every tile joins the search at most once and offers six moves.Space O(n^2) for the chute table, the visited marks and the current set.

Convert the grid into a flat table that gives, for every tile, either -1 or the tile its chute leads to; the back-and-forth numbering is undone by splitting a tile number into how many full rows lie below it and how far along its own row it sits, flipping the direction on alternate rows. Then search outward from tile 1 one turn at a time, expanding the six advances available from each tile in the current set and applying a chute once on arrival. Each tile is entered into the search at most once, so the first time tile n * n appears the number of completed rounds is the answer, and running out of new tiles means it is unreachable.

Pythonentry point: fewest_rolls

def fewest_rolls(board):
    # O(n^2): breadth-first over the tiles, six moves out of each one.
    size = len(board)
    last = size * size

    def where(tile):
        band = (tile - 1) // size
        along = (tile - 1) % size
        row = size - 1 - band
        col = along if band % 2 == 0 else size - 1 - along
        return row, col

    jump = [0] * (last + 1)
    for tile in range(1, last + 1):
        r, c = where(tile)
        jump[tile] = board[r][c]
    seen = [False] * (last + 1)
    seen[1] = True
    frontier = [1]
    turns = 0
    while frontier:
        nxt = []
        for tile in frontier:
            if tile == last:
                return turns
            for step in range(1, 7):
                ahead = tile + step
                if ahead > last:
                    break
                if jump[ahead] != -1:
                    ahead = jump[ahead]
                if not seen[ahead]:
                    seen[ahead] = True
                    nxt.append(ahead)
        frontier = nxt
        turns += 1
    return -1

The obvious version

Give every tile a cost, start tile 1 at zero and every other tile at an impossibly large value, then sweep all tiles over and over, relaxing each of the six advances, until a whole sweep changes nothing.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_rolls(board):
    size = len(board)
    last = size * size
    jump = [0] * (last + 1)
    for tile in range(1, last + 1):
        band = (tile - 1) // size
        along = (tile - 1) % size
        row = size - 1 - band
        col = along if band % 2 == 0 else size - 1 - along
        jump[tile] = board[row][col]
    big = last + 5
    cost = [big] * (last + 1)
    cost[1] = 0
    for _ in range(last + 1):
        moved = False
        for tile in range(1, last + 1):
            if cost[tile] >= big:
                continue
            for step in range(1, 7):
                ahead = tile + step
                if ahead > last:
                    break
                if jump[ahead] != -1:
                    ahead = jump[ahead]
                if cost[tile] + 1 < cost[ahead]:
                    cost[ahead] = cost[tile] + 1
                    moved = True
        if not moved:
            break
    return -1 if cost[last] >= big else cost[last]

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in