Show problems as
Classic problem #63MediumArrayDynamic ProgrammingMatrix

Unique Paths II

Real-world version: Scaffold Deck Routes
Tracked in this browser only
Read Unique Paths II on LeetCode(opens in a new tab)

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

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

Python
def count_deck_routes(deck: list[list[int]]) -> int:
Java
public int countDeckRoutes(int[][] deck)

More on the same topics