A storeroom is drawn as grid, a list of equal-length strings: '#' is a wall or a stack of
shelving, '.' open floor, 'P' the worker, 'B' a heavy crate and 'T' the loading mark on
the floor (one of each; P, B and T stand on open floor).
In one move the worker steps up, down, left or right. Stepping into the crate's cell pushes the crate one cell further in the same direction, which is allowed only if that cell is open floor inside the grid (the loading mark counts as open floor). The worker cannot pull the crate or walk through walls. Walking and pushing both count as one move each.
Return the fewest moves needed until the crate stands on the loading mark, or -1 if that is
impossible.
The setup provides storeroom(rows, cols, seed, clutter=15), which builds a random walled room;
some tests use it. Try it with Run: print("\n".join(storeroom(10, 12, 6))).
Examples
Input: grid = ["P.B.T"]
Output: 3
Explanation: step right, then push the crate right twice.
Input: grid = ["#####",
"#P..#",
"#.B.#",
"#..T#",
"#####"]
Output: 5
Explanation: step down and push right (the crate reaches the column of T), walk up and
right to stand above the crate, and push it down.
Input: grid = ["PB",
"#T"]
Output: -1
Constraints
1 <= len(grid), len(grid[0]) <= 20- the answer never depends on the clock or on randomness
Goals
- Use a pair of positions (worker, crate) as one search state
- Build a heuristic from what every solution must still do