Courier All Stops
Hard · shortest path
A courier is working in a warehouse. The floor plan is a rectangular grid of characters:
"."is open floor and"#"is a wall that cannot be entered."S"is where the courier starts. It appears exactly once and counts as floor."P"is a parcel lying on a floor cell. A parcel is picked up as soon as the courier stands on its cell. There are at most 8 parcels.
Each step moves the courier one cell up, down, left or right, and never outside the grid. The courier may walk over the same cell as often as needed, and may pass over a parcel without any trouble (it is simply picked up on the way).
Return the fewest steps needed to pick up every parcel, in whatever order is best. The courier does not have to come back to the start. If some parcel cannot be reached at all, return -1. If there are no parcels, return 0.
Examples
Example 1
Input: grid = [["S", ".", "P"], ["#", "#", "."], ["P", ".", "."]]
Output: 6
Walk right along the top row to the first parcel (2 steps), then down the right-hand side and along the bottom row to the second one (4 more steps).
Example 2
Input: grid = [["S", "P", "#"], ["#", "#", "P"]]
Output: -1
The parcel in the bottom-right corner is shut off by walls, so it can never be reached.
Example 3
Input: grid = [["P", ".", ".", "S", ".", "P"]]
Output: 7
Going right first costs 2 steps to the right-hand parcel, then 5 steps back to the left-hand one. Going left first would cost 3 + 5 = 8.
Constraints
- 1 <= rows, cols <= 100
- Every cell is ".", "#", "S" or "P".
- There is exactly one "S" and at most 8 "P" cells.
- All rows have the same length.