Rat in a Maze
Intermediate
maze is a grid of 0 (wall) and 1 (open). A rat starts at the top-left cell and must reach the bottom-right cell, moving up, down, left or right through open cells, never visiting a cell twice in the same path.
Return every such path as a string of moves D (down), L (left), R (right), U (up), sorted in dictionary order. If the start or the goal is a wall, or no path exists, return []. If the grid is a single open cell, the one path is the empty string: [""].
Examples
Example 1
Input:
rat_in_a_maze([[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]])
Output:
['DDRDRR', 'DRDDRR']
Example 2
Input:
rat_in_a_maze([[1, 0], [0, 1]])
Output:
[]
Constraints
0 <= rows, cols <= 6- Each cell is
0or1.
Theory
Go to TheoryKeywords
dsa-sheetrecursionbacktracking-puzzles
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.