Rat in a Maze Problem Statement

You need to determine all possible paths for a rat starting at position (0, 0) in a square maze to reach its destination at (N-1, N-1). The maze is represented as an N*N matrix where a cell with value 0 is blocked and value 1 is open for passage. The rat may move in the directions 'U' (up), 'D' (down), 'L' (left), and 'R' (right).

Input:

N (integer representing matrix dimensions)
N lines of N space-separated integers (0 or 1)

Output:

A list of strings, each representing a valid path from source to destination sorted in alphabetical order.
Each path is in the form of a string with directions ('U', 'D', 'L', 'R').

Example:

Input:
4
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1

Output:
['DDRDRR', 'DRDDRR']

Constraints:

• 2 <= N <= 5
• 0 <= MATRIX[i][j] <= 1

Note:

Implement the function to find paths, no need to handle output printing as it's managed elsewhere.