Rat in a Maze
MediumP2Coding
maze is an n x n grid where 1 is an open cell and 0 is a blocked cell. A rat starts at the top-left cell (0, 0) and wants to reach the bottom-right cell (n-1, n-1). It can move down (D), left (L), right (R) or up (U) into an open cell, and it may not visit the same cell twice on one path.
Return all such paths as strings of moves, in any order. If the start or the end is blocked, or no path exists, return an empty array. If the grid is [[1]] the rat is already at the goal and the only path is the empty string "".
Example 1
- Input
- maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]
- Output
- ["DDRDRR","DRDDRR"]
- Why
- Two routes reach the corner: DDRDRR and DRDDRR.
Example 2
- Input
- maze = [[1]]
- Output
- [""]
- Why
- The rat already stands on the goal, so the only path is the empty string.
Example 3
- Input
- maze = [[0]]
- Output
- []
Constraints
- 1 <= n <= 6
maze[i][j]is 0 or 1
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.