0262MediumArrayDynamic ProgrammingMatrix

Scaffold Deck Routes

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 rigging crew works on a scaffold deck laid out as a rectangle of square panels. You are given deck, where deck[r][c] is 1 when that panel is stacked with material and cannot be stepped on, and 0 when the panel is clear.

A crew member stands on the north-west panel deck[0][0] and has to end up on the south-east panel. Each step moves onto the panel immediately east or the panel immediately south of the one being stood on, and every panel stepped on has to be clear.

Return how many different step sequences take the crew member from the north-west panel to the south-east panel. If either of those two corner panels is stacked, no sequence exists and the count is 0.

Examples

Example 1

Input: deck = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0]]
Output: 4

The stacked panels are `deck[1][1]` and `deck[2][3]`. Four step sequences stay on clear panels, one of them being east, east, south, south, south, east.

Example 2

Input: deck = [[0, 1, 0], [0, 0, 0]]
Output: 1

Only south, east, east keeps to clear panels: any sequence that opens with a step east lands on the stacked panel `deck[0][1]`.

Example 3

Input: deck = [[1, 0], [0, 0]]
Output: 0

The north-west panel is itself stacked, so the crew member has nowhere to stand at the start and no sequence can be counted.

Constraints

rows == deck.length
cols == deck[0].length
1 <= rows, cols <= 100
deck[r][c] is 0 or 1

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 count_deck_routes(deck: list[list[int]]) -> int:

Java

public int countDeckRoutes(int[][] deck)

The intended approach

Time O(rows * cols)Space O(cols) for the single row of counts

Sweep the deck row by row carrying a single array `ways`, where `ways[c]` holds the number of step sequences that reach the panel in column `c` of the row being processed. When the sweep arrives at a clear panel, `ways[c]` already counts the sequences that came from the north, so adding `ways[c - 1]` folds in the ones that came from the west; a stacked panel is unreachable and its entry drops to zero, which is what stops sequences from passing through it. Column 0 has no western neighbour and only inherits from the north, and after the final row the entry for the last column is the answer. A stacked north-west panel is settled before the sweep starts, since there would be nothing to seed the first entry with.

Pythonentry point: count_deck_routes

def count_deck_routes(deck):
    rows = len(deck)
    cols = len(deck[0])
    if deck[0][0] == 1:
        return 0
    ways = [0] * cols
    ways[0] = 1
    for r in range(rows):
        for c in range(cols):
            if deck[r][c] == 1:
                ways[c] = 0
            elif c > 0:
                ways[c] += ways[c - 1]
    return ways[cols - 1]

The obvious version

Walk out every step sequence one at a time from an explicit stack of partial positions and tally each arrival at the south-east panel, so a panel reachable by several sequences is expanded once per sequence. Exponential in the size of the deck, but it counts sequences by construction.

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_count_deck_routes(deck):
    rows = len(deck)
    cols = len(deck[0])
    if deck[0][0] == 1 or deck[rows - 1][cols - 1] == 1:
        return 0
    total = 0
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == rows - 1 and c == cols - 1:
            total += 1
            continue
        if r + 1 < rows and deck[r + 1][c] == 0:
            stack.append((r + 1, c))
        if c + 1 < cols and deck[r][c + 1] == 0:
            stack.append((r, c + 1))
    return total

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