Shortest Route Through a Traced Maze
Duolingo● MediumNEW GRADINTERNOAProblem statement
Duo records one route through a maze as a list path whose entries are "north", "east", "south", or "west". The route begins at coordinate (0, 0).
Every cell visited by the recorded route is known to be passable. No unvisited cell may be inferred to be passable. Two known cells are connected when they are orthogonally adjacent.
The source guarantees that there is exactly one shortest route through the known cells from (0, 0) to the recorded route's final coordinate. Return that route as a list of direction strings. The result may equal path when the recorded route is already optimal.
Function
shortestTracedMazeRoute(path: String[]) → String[]Examples
Example 1
path = ["south","east","east","south","south","west","west","east","east","south"]return = ["south","east","east","south","south","south"]The recorded walk visits cells that create a direct vertical connection near the end. The unique shortest known route removes the west-east detour and uses six moves instead of ten.
Constraints
1 <= path.length <= 100000.- Every entry is exactly
"north","east","south", or"west". - The source guarantees exactly one shortest route through the visited cells from the origin to the final coordinate.
- The returned route is never longer than
path.
Source note: The added source image shows the maze prompt, recorded route, and shorter-route example from an independent Duolingo OA report.