Show problems as
Classic problem #3552MediumArrayHash TableBreadth-First SearchMatrix

Grid Teleportation Traversal

Real-world version: Picker Route With Warehouse Chutes
Tracked in this browser only
Read Grid Teleportation Traversal on LeetCode(opens in a new tab)

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

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

More on the same topics