Sort by

recency

|

54 Discussions

|

  • + 0 comments

    Complexity is O(N * M * dest_I * dest_J) if there is a solution (i.e. k >= dest.I + dest.J) and O(1) if there is none. miniature dachshund

  • + 0 comments

    BFS Solution

    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];
        }
    
  • + 0 comments

    recursion on the length of path, O(n*m*k)

    int coinOnTheTable(int n, int m, int K, int P1, int P2, const vector<vector<char>>& board) {
        vector<vector<vector<int>>> cache(n + 2, vector<vector<int>>(m + 2, vector<int>(K + 1, 10000)));
        cache[1][1][0] = 0;
        for (int t = 1; t <= K; t++) {
            cache[1][1][t] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (i == 1 and j == 1) continue;
                    int left = (board[i][j - 1] == 'R') ? cache[i][j - 1][t - 1] : cache[i][j - 1][t - 1] + 1;
                    int right = (board[i][j + 1] == 'L') ? cache[i][j + 1][t - 1] : cache[i][j + 1][t - 1] + 1;
                    int up = (board[i - 1][j] == 'D') ? cache[i - 1][j][t - 1] : cache[i - 1][j][t - 1] + 1;
                    int down = (board[i + 1][j] == 'U') ? cache[i + 1][j][t - 1] : cache[i + 1][j][t - 1] + 1;
                    cache[i][j][t] = min({ left, right, up, down });
                }
            }
        }
        return (cache[P1][P2][K] <= 2601) ? cache[P1][P2][K] : -1;
    }
    
    int main()
    {
        int n, m, K, P1, P2;
        string s;
        cin >> n >> m >> K;
        vector<vector<char>> board(n + 2, vector<char>(m + 2));
        for (int i = 1; i <= n; i++) {
            cin >> s;
            for (int j=1; j <= s.size(); j++) {
                board[i][j] = s[j - 1];
                if (s[j-1] == '*') {
                    P1 = i;
                    P2 = j;
                }
            }
        }
        cout << coinOnTheTable(n, m, K, P1, P2, board);
    }
    
  • + 0 comments

    You should use stone center table for the coin toss purpose as it is more reliable and best metrial in it.

  • + 0 comments

    Coin on the Table" is a mathematical game often presented as a puzzle. The game involves a grid or table filled with coins, and the objective is to determine the minimum number of moves required to rearrange the coins to satisfy a certain condition for Lost ark eng cal. The condition typically involves moving a coin from one cell to another with the goal of reaching a desired arrangement.

    The specific rules and conditions of the "Coin on the Table" puzzle can vary, but here's a general description of how the game is often played:

    Game Setup:

    The game is played on a grid or table. Each cell of the grid contains a coin, and the coins can be facing heads or tails. One cell is usually marked as the starting position, and another cell is designated as the target or goal position.