class Solution {
    public static boolean valid(int r,int c,int n,int m){
        if(r<0 || r>=n || c<0 || c>=m){
            return false;
        }
        return true;
    }
    static int[] x={0 ,0,-1,1};
    static int[] y={-1,1,0,0};
 
    public int[] lastVisitedCell(char[][] grid) {
        int n=grid.length;//rows
        int m=grid[0].length; //columns
 
        boolean[][] visited = new boolean[n][m];
 
        int[]res = new int[2];
        dfs(grid,0,0,visited,res);
 
        return res;
    }
 
    public static void dfs(char[][] grid,int r,int c, boolean[][] visited,int[]res){
 
        int n=grid.length;//rows
        int m=grid[0].length; //columns
 
        visited[r][c]=true;
 
        res[0]=r;
        res[1]=c;
 
        int k=0;
 
        if(grid[r][c] =='L'){
            k=0;
        }
        else if(grid[r][c] == 'R'){
            k=1;
        }
        else if(grid[r][c] == 'U'){
            k=2;
        }
        else if(grid[r][c] == 'D'){
            k=3;
        }
 
        int nr=r+x[k];
        int nc=c+y[k];
 
        if(valid(nr,nc,n,m) && !visited[nr][nc]){
            dfs(grid,nr,nc,visited,res);
        }
    }
}

Y2xhc3MgU29sdXRpb24gewogICAgcHVibGljIHN0YXRpYyBib29sZWFuIHZhbGlkKGludCByLGludCBjLGludCBuLGludCBtKXsKICAgICAgICBpZihyPDAgfHwgcj49biB8fCBjPDAgfHwgYz49bSl7CiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CiAgICBzdGF0aWMgaW50W10geD17MCAsMCwtMSwxfTsKICAgIHN0YXRpYyBpbnRbXSB5PXstMSwxLDAsMH07CgogICAgcHVibGljIGludFtdIGxhc3RWaXNpdGVkQ2VsbChjaGFyW11bXSBncmlkKSB7CiAgICAgICAgaW50IG49Z3JpZC5sZW5ndGg7Ly9yb3dzCiAgICAgICAgaW50IG09Z3JpZFswXS5sZW5ndGg7IC8vY29sdW1ucwogICAgICAgIAogICAgICAgIGJvb2xlYW5bXVtdIHZpc2l0ZWQgPSBuZXcgYm9vbGVhbltuXVttXTsKCiAgICAgICAgaW50W11yZXMgPSBuZXcgaW50WzJdOwogICAgICAgIGRmcyhncmlkLDAsMCx2aXNpdGVkLHJlcyk7CgogICAgICAgIHJldHVybiByZXM7CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIGRmcyhjaGFyW11bXSBncmlkLGludCByLGludCBjLCBib29sZWFuW11bXSB2aXNpdGVkLGludFtdcmVzKXsKCiAgICAgICAgaW50IG49Z3JpZC5sZW5ndGg7Ly9yb3dzCiAgICAgICAgaW50IG09Z3JpZFswXS5sZW5ndGg7IC8vY29sdW1ucwoKICAgICAgICB2aXNpdGVkW3JdW2NdPXRydWU7CgogICAgICAgIHJlc1swXT1yOwogICAgICAgIHJlc1sxXT1jOwoKICAgICAgICBpbnQgaz0wOwoKICAgICAgICBpZihncmlkW3JdW2NdID09J0wnKXsKICAgICAgICAgICAgaz0wOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGdyaWRbcl1bY10gPT0gJ1InKXsKICAgICAgICAgICAgaz0xOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGdyaWRbcl1bY10gPT0gJ1UnKXsKICAgICAgICAgICAgaz0yOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGdyaWRbcl1bY10gPT0gJ0QnKXsKICAgICAgICAgICAgaz0zOwogICAgICAgIH0KCiAgICAgICAgaW50IG5yPXIreFtrXTsKICAgICAgICBpbnQgbmM9Yyt5W2tdOwoKICAgICAgICBpZih2YWxpZChucixuYyxuLG0pICYmICF2aXNpdGVkW25yXVtuY10pewogICAgICAgICAgICBkZnMoZ3JpZCxucixuYyx2aXNpdGVkLHJlcyk7CiAgICAgICAgfQogICAgfQp9