Bend-free pipeline
MediumOnline Assessment
Find the route with the fewest bends for a water pipe through a walled-in factory floor.
plan is a list of equal-length strings describing the floor, one string per row. "." is open floor, "#" is a wall, "S" is where the pipe starts and "E" is where it must end. The pipe is built as a chain of unit steps, each moving to a side-adjacent cell (up, down, left or right) that is not a wall. A step may enter S and E like any open cell.
A bend is a place where two consecutive steps go in different directions. The first step can point in any direction and never counts as a bend. A pipe is allowed to cross over cells it already uses, and its length does not matter: only the number of bends does.
Input: plan, the floor plan.
Output: the smallest possible number of bends in a pipe from S to E, or -1 if no pipe can be built. A straight pipe has 0 bends.
The floor can be 100 x 100 with long winding corridors, so a solution that keeps re-checking every cell until nothing improves will be too slow.
Example 1
- Input:
- [["S..E",".##.","...."]]
- Output:
- 0
- Explanation
- The open row at the top leads straight from S to E with no turn at all, so the answer is 0.
Example 2
- Input:
- [["S#....","...#..",".#..#.","..#...","#..##E"]]
- Output:
- 4
- Explanation
- The only shortest route has 9 steps, but it zigzags and bends 6 times. A longer route is better: down one cell, right to column 2, up one cell, right along the top row to the last column, then straight down to E. It bends only 4 times (the pipe may be longer, only bends count), so the answer is 4.
Example 3
- Input:
- [["S#E","..#","..."]]
- Output:
- -1
- Explanation
- The pipe cannot pass the wall column at all, so there is no route and the answer is -1.
Constraints
2 <= plan.length <= 100rows, all of the same length1 <= plan[i].length <= 100- every character is
".","#","S"or"E", and"S"and"E"each appear exactly once