static class QueueEntry {
        int x;
        int y;
        int t;
        int cost;
        public QueueEntry(int x, int y, int t, int cost) {
            this.x = x;
            this.y = y;
            this.t = t;
            this.cost = cost;
        }

    }
    static int[][] dirs = {{1,0},
            {-1,0},
            {0,1},
            {0,-1},
            {0, 0}};

    static boolean isMovePossible(int x, int y, int x1, int y1, char move) {
        return (move == 'U' && x1 == x - 1 && y1 == y)
                || (move == 'D' && x1 == x + 1 && y1 == y)
                || (move == 'L' && x1 == x && y1 == y - 1)
                || (move == 'R' && x1 == x && y1 == y + 1);
    }

    public static int coinOnTheTable(int m, int k, List<String> board) {
        if(board.isEmpty()) {
            return -1;
        }
        int r=0,c=0;
        int[][] minCost = new int[board.size()][board.get(0).length()];
        for(int i=0; i<board.size(); i++) {
            for(int j=0; j<board.get(i).length(); j++) {
                minCost[i][j] = Integer.MAX_VALUE;
                if (board.get(i).charAt(j) == '*') {
                    r = i;
                    c = j;
                }
            }
        }
        Queue<QueueEntry> pq = new LinkedList<>();
        pq.add(new QueueEntry(0,0,0,0));

        minCost[0][0] = 0;
        while(!pq.isEmpty()) {
            QueueEntry curr = pq.poll();
            char currChar = board.get(curr.x).charAt(curr.y);
            for(int[] dir: dirs) {
                int x1 = curr.x + dir[0];
                int y1 = curr.y + dir[1];
                if(x1>=0 && x1<board.size() && y1>=0 && y1<m
                        && curr.t+1 <= k) {
                    int cost = isMovePossible(curr.x, curr.y, x1, y1, currChar) ? curr.cost : curr.cost + 1;
                    if(cost < minCost[x1][y1]) {
                        pq.add(new QueueEntry(x1, y1, curr.t + 1, cost));
                        minCost[x1][y1] = cost;

                    }
                }
            }
        }
        return minCost[r][c] == Integer.MAX_VALUE ? -1 : minCost[r][c];
    }