0732MediumArrayHash TableBreadth-First SearchMatrix

Picker Route With Warehouse Chutes

Tracked in this browser only

Trains the technique from

LeetCode 3552Grid Teleportation Traversal

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 warehouse floor is given as floor, a list of strings of equal length listed from the top row downwards, so floor[r][c] is the cell in row r and column c. Each character is one of:

"#", a rack that cannot be entered;
".", plain open floor;
an uppercase letter, open floor holding a chute marked with that letter.

Write m for how many strings floor holds and n for their common length. A picker starts on cell (0, 0), which is never a rack, and the pick face is the last cell of the last row, row m - 1 and column n - 1.

One move goes from the current cell to a cell sharing an edge with it, up, down, left or right, as long as that cell is inside the floor and is not a rack. Each move counts as one.

Chutes give a second way to travel. Standing on a cell that holds a chute, the picker may drop through it and climb out on any other cell holding a chute marked with the same letter, which counts as no moves at all. Over the whole route the picker may drop through at most one chute of each letter: once a letter has been used, the chutes marked with it are sealed for the rest of the route. Chutes never have to be used.

Return the fewest moves the picker needs to get from its starting cell to the pick face, or -1 when there is no way through.

Examples

Example 1

Input: floor = ["A#", "#A"]
Output: 0

Both cells beside the start are racks, but the start holds an A chute and so does the pick face, so dropping through lands the picker on the pick face without a single move.

Example 2

Input: floor = ["A.B", "###", "A.B"]
Output: 2

The middle row is solid rack. Dropping through the A chute at the start comes out at the A chute in the bottom row, and two steps to the right along that row reach the pick face.

Example 3

Input: floor = [".#", "#."]
Output: -1

The two cells beside the start are racks and there is no chute anywhere, so the pick face cannot be reached.

Constraints

1 <= floor.length <= 1000
1 <= floor[i].length <= 1000
Every string in floor has the same length.
Each character of floor is "#", ".", or an uppercase English letter.
floor[0][0] is not "#".

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_moves(floor: list[str]) -> int:

Java

public int fewestMoves(String[] floor)

The intended approach

Time O(m * n) for an m by n floor, since each cell is settled once and each letter group is opened once.Space O(m * n) for the cost grid, the settled flags and the queue.

Costs are only 0 and 1, so a breadth-first sweep on a double-ended queue is enough: a neighbouring step is pushed to the back with cost one more, while the cells opened by a chute are pushed to the front with the same cost. That keeps the queue holding at most two different costs, so the first time a cell leaves the queue its cost is final. The first cell of a given letter to leave the queue is therefore the cheapest cell of that letter, which is where the single allowed drop for that letter should be taken from, so the whole group is opened at that moment and the letter is then retired. The sweep stops when the bottom-right cell leaves the queue, and reports -1 if the queue empties first.

Pythonentry point: fewest_moves

def fewest_moves(floor):
    # A step costs 1 and a chute drop costs 0, so the search is a breadth-first
    # sweep on a double-ended queue: drops go on the front, steps on the back, which
    # keeps the queue in order of cost and makes the first time a cell comes off the
    # queue its final cost.  The cheapest cell of a letter is therefore the first of
    # that letter to come off, so opening the whole letter at that moment and then
    # retiring the letter covers the one drop the letter is allowed.
    # Time O(m * n).  Space O(m * n).
    from collections import deque
    rows = len(floor)
    cols = len(floor[0])
    if floor[rows - 1][cols - 1] == "#":
        return -1
    chutes = {}
    for r in range(rows):
        line = floor[r]
        for c in range(cols):
            ch = line[c]
            if "A" <= ch <= "Z":
                if ch in chutes:
                    chutes[ch].append((r, c))
                else:
                    chutes[ch] = [(r, c)]
    far = rows * cols + 1
    cost = [[far] * cols for _ in range(rows)]
    settled = [[False] * cols for _ in range(rows)]
    used = set()
    cost[0][0] = 0
    pending = deque([(0, 0)])
    while pending:
        r, c = pending.popleft()
        if settled[r][c]:
            continue
        settled[r][c] = True
        here = cost[r][c]
        if r == rows - 1 and c == cols - 1:
            return here
        mark = floor[r][c]
        if "A" <= mark <= "Z" and mark not in used:
            used.add(mark)
            for rr, cc in chutes[mark]:
                if not settled[rr][cc] and here < cost[rr][cc]:
                    cost[rr][cc] = here
                    pending.appendleft((rr, cc))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r + dr
            nc = c + dc
            if 0 <= nr < rows and 0 <= nc < cols and floor[nr][nc] != "#":
                if not settled[nr][nc] and here + 1 < cost[nr][nc]:
                    cost[nr][nc] = here + 1
                    pending.append((nr, nc))
    return -1

The obvious version

Keep a cost per cell and relax repeatedly until nothing changes: one pass pushes cost through every edge between neighbouring open cells, and one pass levels every letter group down to the cheapest cell in it. Repeating both passes to a standstill leaves the cost of the bottom-right cell.

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_moves(floor):
    rows = len(floor)
    cols = len(floor[0])
    if floor[rows - 1][cols - 1] == "#":
        return -1
    far = float("inf")
    dist = [[far] * cols for _ in range(rows)]
    dist[0][0] = 0
    groups = {}
    for r in range(rows):
        for c in range(cols):
            ch = floor[r][c]
            if "A" <= ch <= "Z":
                groups.setdefault(ch, []).append((r, c))
    changed = True
    while changed:
        changed = False
        for r in range(rows):
            for c in range(cols):
                if dist[r][c] == far or floor[r][c] == "#":
                    continue
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and floor[nr][nc] != "#":
                        if dist[r][c] + 1 < dist[nr][nc]:
                            dist[nr][nc] = dist[r][c] + 1
                            changed = True
        for cells in groups.values():
            low = far
            for r, c in cells:
                if dist[r][c] < low:
                    low = dist[r][c]
            for r, c in cells:
                if low < dist[r][c]:
                    dist[r][c] = low
                    changed = True
    answer = dist[rows - 1][cols - 1]
    if answer == far:
        return -1
    return answer

How this problem was checked

Reference solution executed against 19 test cases — 19 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