# rat in maze 2

```java
import java.util.*;

class Solution {
    public static ArrayList<String> findPath(int[][] m, int n) {
        ArrayList<String> res = new ArrayList<>();
        
        // If start or end is blocked
        if (m[0][0] == 0 || m[n - 1][n - 1] == 0) return res;

        dfs(m, n, 0, 0, "", res);
        Collections.sort(res);
        return res;
    }
    private static void dfs(int[][] m, int n, int row, int col, String path, ArrayList<String> res) {
        // Base case: reached destination
        if (row == n - 1 && col == n - 1) {
            res.add(path);
            return;
        }

        // Mark current cell as visited by changing it to -1
        m[row][col] = -1;

        // Direction vectors and corresponding letters
        int[] dx = {+1, 0, 0, -1}; // Down, Left, Right, Up
        int[] dy = {0, -1, +1, 0};
        char[] dir = {'D', 'L', 'R', 'U'};

        for (int i = 0; i < 4; i++) {
            int newRow = row + dx[i];
            int newCol = col + dy[i];

            if (isSafe(newRow, newCol, m, n)) {
                dfs(m, n, newRow, newCol, path + dir[i], res);
            }
        }

        // Backtrack: unmark the cell
        m[row][col] = 1;
    }

    private static boolean isSafe(int x, int y, int[][] m, int n) {
        return x >= 0 && x < n && y >= 0 && y < n && m[x][y] == 1;
    }
}
```