A Crate in the Warehouse

Hard

A warehouse plan is a grid floor of characters: - '.' is an empty cell; - '#' is a wall; - 'S' is the worker; - 'B' is the crate; - 'T' is where the crate has to end up. The worker walks up, down, left and right over empty cells (the 'S' and 'T' cells count as empty). Walls and the crate cannot be walked through. To move the crate, the worker stands next to it and steps toward it: the crate slides one cell in the same direction, as long as that cell is not a wall or outside the warehouse. That is one push. Return the fewest pushes needed to get the crate onto the 'T' cell, or -1 if it cannot be done. The worker's own steps are not counted.

Example 1

floor=[['#', '#', '#', '#', '#'], ['#', 'T', '.', '.', '#'], ['#', '.', 'B', '.', '#'], ['#', '.', '.', 'S', '#'], ['#', '#', '#', '#', '#']] → 2

The worker steps below the crate and pushes it up, then walks around to its right and pushes it left: 2 pushes.

Example 2

floor=[['#', '#', '#', '#', '#', '#'], ['#', 'T', '.', 'B', 'S', '#'], ['#', '#', '#', '#', '#', '#']] → 2

The corridor is narrow, but the crate only has to go left: two pushes in a row.

Example 3

floor=[['#', '#', '#', '#', '#'], ['#', 'S', 'B', 'T', '#'], ['#', '#', '#', '#', '#']] → 1

Constraints

1 ≤ len(floor), len(floor[0]) ≤ 20
all rows of the grid have the same length
floor[i][j] is one of '.', '#', 'S', 'B', 'T'
'S', 'B' and 'T' each appear exactly once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Matrix Heap (Priority Queue)

Similar problems

Rain Pools on a Relief Map Hard Ball Into the Hole Hard Trim the Bushes, Shortest First Hard Crossing at High Tide Hard Repaint Arrows to Reach the Exit Hard

Input

floor=[['#', '#', '#', '#', '#'], ['#', 'T', '.', '.', '#'], ['#', '.', 'B', '.', '#'], ['#', '.', '.', 'S', '#'], ['#', '#', '#', '#', '#']]

Expected

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.