Description: A rat is placed at position (0, 0) in an n × n square matrix maze[][]. The goal is to reach the destination (n-1, n-1). Each cell contains:
1 ? free cell (can move)
0 ? blocked cell (cannot move)
The rat can move in four directions:
U (Up), D (Down), L (Left), R (Right)
The rat cannot visit the same cell more than once in a path and can only move inside the grid through free cells.
Return all valid paths in lexicographically sorted order. If no path exists, return an empty list.
Example 1
Input: maze[][] = [ [1, 1], [1, 1] ]
Output: ["DR", "RD"]
Explanation: The rat can reach the destination by moving Down?Right or Right?Down.
Example 2
Input: maze[][] = [ [1, 0, 0], [1, 1, 0], [0, 1, 1] ]
Output: ["DRDR"]
Explanation: Only one valid path exists through the open cells.
Example 3
Input: maze[][] = [ [1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1] ]
Output: ["DDRDRR", "DRDDRR"]
Explanation: Multiple valid routes reach the destination; after sorting, both paths are returned.
Sign in to write, run, and submit your solution against the full test suite.