638. Maze Routes
A small maze is given as a grid where 0 is an open cell and 1 is a wall. A walker starts in the top-left cell and wants to reach the bottom-right cell. In one move the walker steps to an open neighbour: D (down), L (left), R (right) or U (up). A route may not visit any cell twice.
Return every possible route as a string of moves, sorted in increasing alphabetical order (so D comes before L, then R, then U). If the start or the target is a wall, or no route exists, return an empty list. If the maze has a single open cell, the walker is already at the target and the only route is the empty string.
Example 1
- Input:
- maze = [[0,0],[0,0]]
- Output:
- ["DR","RD"]
- Explanation:
Two routes exist: down then right (
DR) and right then down (RD). In alphabetical orderDRcomes first.
Example 2
- Input:
- maze = [[0,1],[1,0]]
- Output:
- []
- Explanation:
Both cells next to the start are walls, so the target cannot be reached.
Example 3
- Input:
- maze = [[0,0,0],[1,1,0],[0,0,0]]
- Output:
- ["RRDD"]
- Explanation:
The only way is across the top row, down the right column:
RRDD.
Constraints
- 1 ≤ number of rows, number of columns ≤ 4
- Every cell is 0 or 1.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(3^(R*C)) in the worst case
- Space
- O(R * C)