1class Solution {
2    public int minCost(int[][] grid, int k) {
3        int rows = grid.length, cols = grid[0].length;
4        // Use a "large enough" value to represent infinity while avoiding overflow during addition
5        int inf = Integer.MAX_VALUE / 2;
6
7        // dp[t][i][j] = minimum cost to reach cell (i, j) using exactly (at most) t teleports
8        int[][][] dp = new int[k + 1][rows][cols];
9        for (int t = 0; t <= k; t++) {
10            for (int i = 0; i < rows; i++) {
11                Arrays.fill(dp[t][i], inf);
12            }
13        }
14
15        // --- Base case: t = 0 (no teleports used) ---
16        // Starting point cost is 0
17        dp[0][0][0] = 0;
18        for (int i = 0; i < rows; i++) {
19            for (int j = 0; j < cols; j++) {
20                // Move down from the cell above
21                if (i > 0) {
22                    dp[0][i][j] = Math.min(dp[0][i][j], dp[0][i - 1][j] + grid[i][j]);
23                }
24                // Move right from the cell on the left
25                if (j > 0) {
26                    dp[0][i][j] = Math.min(dp[0][i][j], dp[0][i][j - 1] + grid[i][j]);
27                }
28            }
29        }
30
31        // --- Group cell coordinates by their grid value ---
32        // A teleport can jump between any two cells that share the same value
33        Map<Integer, List<int[]>> valueToCells = new HashMap<>();
34        for (int i = 0; i < rows; i++) {
35            for (int j = 0; j < cols; j++) {
36                int value = grid[i][j];
37                valueToCells.computeIfAbsent(value, key -> new ArrayList<>())
38                            .add(new int[] {i, j});
39            }
40        }
41
42        // Sort the distinct values in descending order.
43        // Processing larger values first lets us carry forward the running minimum,
44        // so a teleport from a higher value can reach any cell with a value <= it.
45        List<Integer> sortedValues = new ArrayList<>(valueToCells.keySet());
46        sortedValues.sort(Collections.reverseOrder());
47
48        // --- Transition for each teleport count t (1..k) ---
49        for (int t = 1; t <= k; t++) {
50            // runningMin tracks the best dp value (using t-1 teleports) among all cells
51            // whose value is >= the current value group being processed.
52            int runningMin = inf;
53            for (int value : sortedValues) {
54                List<int[]> cells = valueToCells.get(value);
55
56                // Update the running minimum with the best cost to arrive at any cell
57                // in this value group using t-1 teleports.
58                for (int[] cell : cells) {
59                    runningMin = Math.min(runningMin, dp[t - 1][cell[0]][cell[1]]);
60                }
61
62                // Teleporting into any cell of this group costs the same as the
63                // accumulated minimum (no movement cost for the teleport itself).
64                for (int[] cell : cells) {
65                    dp[t][cell[0]][cell[1]] = runningMin;
66                }
67            }
68
69            // After applying teleports, relax with normal down/right moves
70            // so the teleport landing spots can propagate further.
71            for (int i = 0; i < rows; i++) {
72                for (int j = 0; j < cols; j++) {
73                    if (i > 0) {
74                        dp[t][i][j] = Math.min(dp[t][i][j], dp[t][i - 1][j] + grid[i][j]);
75                    }
76                    if (j > 0) {
77                        dp[t][i][j] = Math.min(dp[t][i][j], dp[t][i][j - 1] + grid[i][j]);
78                    }
79                }
80            }
81        }
82
83        // --- Collect the answer ---
84        // The optimal solution may use anywhere from 0 to k teleports.
85        int ans = inf;
86        for (int t = 0; t <= k; t++) {
87            ans = Math.min(ans, dp[t][rows - 1][cols - 1]);
88        }
89        return ans;
90    }
91}
92

1class Solution {
2public:
3    int minCost(vector<vector<int>>& grid, int k) {
4        int rows = grid.size(), cols = grid[0].size();
5        const int kInf = INT_MAX / 2;
6
7        // dp[t][i][j]: minimum cost to reach cell (i, j) using exactly t teleport operations.
8        vector<vector<vector<int>>> dp(
9            k + 1, vector<vector<int>>(rows, vector<int>(cols, kInf)));
10
11        // Base case: starting cell with zero teleports.
12        dp[0][0][0] = 0;
13
14        // Fill the layer with 0 teleports using only normal down/right moves.
15        for (int i = 0; i < rows; i++) {
16            for (int j = 0; j < cols; j++) {
17                if (i > 0) {
18                    dp[0][i][j] = min(dp[0][i][j], dp[0][i - 1][j] + grid[i][j]);
19                }
20                if (j > 0) {
21                    dp[0][i][j] = min(dp[0][i][j], dp[0][i][j - 1] + grid[i][j]);
22                }
23            }
24        }
25
26        // Group every cell coordinate by its grid value.
27        unordered_map<int, vector<pair<int, int>>> valueToCells;
28        for (int i = 0; i < rows; i++) {
29            for (int j = 0; j < cols; j++) {
30                int value = grid[i][j];
31                valueToCells[value].push_back({i, j});
32            }
33        }
34
35        // Collect all distinct values and sort them in descending order so that
36        // cheaper buckets can inherit the minimum cost from more expensive ones.
37        vector<int> sortedKeys;
38        sortedKeys.reserve(valueToCells.size());
39        for (auto& entry : valueToCells) {
40            sortedKeys.push_back(entry.first);
41        }
42        sort(sortedKeys.begin(), sortedKeys.end(), greater<int>());
43
44        // Compute each teleport layer t from 1 to k.
45        for (int t = 1; t <= k; t++) {
46            int runningMin = kInf;
47
48            // Process value buckets from largest to smallest value.
49            // A teleport into a bucket can come from any cell with a value
50            // greater than or equal to it (already merged into runningMin).
51            for (int key : sortedKeys) {
52                auto& cells = valueToCells[key];
53
54                // Update the running minimum with the best cost (using t-1 teleports)
55                // among all cells in the current bucket.
56                for (auto& cell : cells) {
57                    runningMin = min(runningMin, dp[t - 1][cell.first][cell.second]);
58                }
59
60                // Teleport into every cell of this bucket with the running minimum cost.
61                for (auto& cell : cells) {
62                    dp[t][cell.first][cell.second] = runningMin;
63                }
64            }
65
66            // After teleporting, relax this layer again with normal down/right moves.
67            for (int i = 0; i < rows; i++) {
68                for (int j = 0; j < cols; j++) {
69                    if (i > 0) {
70                        dp[t][i][j] = min(dp[t][i][j], dp[t][i - 1][j] + grid[i][j]);
71                    }
72                    if (j > 0) {
73                        dp[t][i][j] = min(dp[t][i][j], dp[t][i][j - 1] + grid[i][j]);
74                    }
75                }
76            }
77        }
78
79        // The answer is the minimum cost to reach the bottom-right cell
80        // using any number of teleports from 0 to k.
81        int answer = kInf;
82        for (int t = 0; t <= k; t++) {
83            answer = min(answer, dp[t][rows - 1][cols - 1]);
84        }
85        return answer;
86    }
87};
88

1// The smallest possible cost; used as a sentinel for "unreachable" states.
2const INF = 1e18;
3
4/**
5 * Computes the minimum cost to travel from the top-left cell to the
6 * bottom-right cell of `grid`, where at most `k` "teleport" operations may be
7 * used.
8 *
9 * Movement rules:
10 *  - You may move from a cell to an adjacent cell (down or right), paying the
11 *    cost of the cell you move into.
12 *  - You may also "teleport" from any cell to any other cell that has a
13 *    strictly smaller (or equal, handled greedily) grid value for free, but
14 *    each such teleport consumes one of the `k` allowed operations.
15 *
16 * The dynamic programming state is:
17 *   f[t][i][j] = minimum cost to reach cell (i, j) having used exactly `t`
18 *                teleport operations.
19 *
20 * @param grid The 2D cost grid.
21 * @param k    The maximum number of teleport operations allowed.
22 * @returns    The minimum total cost to reach the bottom-right corner.
23 */
24function minCost(grid: number[][], k: number): number {
25    // Grid dimensions: `rows` x `cols`.
26    const [rows, cols] = [grid.length, grid[0].length];
27
28    // f[t][i][j] = min cost to reach (i, j) using exactly `t` teleports.
29    // Initialize every state to INF (unreachable).
30    const f: number[][][] = Array.from({ length: k + 1 }, () =>
31        Array.from({ length: rows }, () => Array<number>(cols).fill(INF)),
32    );
33
34    // Base case: starting cell with zero teleports costs nothing.
35    f[0][0][0] = 0;
36
37    // Layer t = 0: pure walking (down/right) with no teleports.
38    for (let i = 0; i < rows; i++) {
39        for (let j = 0; j < cols; j++) {
40            // Arrive from the cell above.
41            if (i > 0) {
42                f[0][i][j] = Math.min(f[0][i][j], f[0][i - 1][j] + grid[i][j]);
43            }
44            // Arrive from the cell on the left.
45            if (j > 0) {
46                f[0][i][j] = Math.min(f[0][i][j], f[0][i][j - 1] + grid[i][j]);
47            }
48        }
49    }
50
51    // Group cell coordinates by their grid value so teleport targets sharing
52    // a value can be processed together.
53    const valueToPositions = new Map<number, Array<[number, number]>>();
54    for (let i = 0; i < rows; i++) {
55        for (let j = 0; j < cols; j++) {
56            const value = grid[i][j];
57            if (!valueToPositions.has(value)) {
58                valueToPositions.set(value, []);
59            }
60            valueToPositions.get(value)!.push([i, j]);
61        }
62    }
63
64    // Distinct grid values sorted in descending order. Processing from large
65    // to small lets us accumulate the best previously-reachable cost (`best`)
66    // and propagate it to cells with smaller values via a teleport.
67    const sortedValues = Array.from(valueToPositions.keys()).sort((a, b) => b - a);
68
69    // Build each teleport layer t = 1 .. k.
70    for (let t = 1; t <= k; t++) {
71        // Best cost found so far among cells with a value >= the current one,
72        // taken from the previous teleport layer.
73        let best = INF;
74
75        for (const value of sortedValues) {
76            const positions = valueToPositions.get(value)!;
77
78            // Update `best` using all cells of this value from layer t - 1.
79            for (const [x, y] of positions) {
80                best = Math.min(best, f[t - 1][x][y]);
81            }
82            // Teleport into every cell of this value at cost `best`.
83            for (const [x, y] of positions) {
84                f[t][x][y] = best;
85            }
86        }
87
88        // After teleporting, allow normal walking within this layer.
89        for (let i = 0; i < rows; i++) {
90            for (let j = 0; j < cols; j++) {
91                // Arrive from the cell above.
92                if (i > 0) {
93                    f[t][i][j] = Math.min(f[t][i][j], f[t][i - 1][j] + grid[i][j]);
94                }
95                // Arrive from the cell on the left.
96                if (j > 0) {
97                    f[t][i][j] = Math.min(f[t][i][j], f[t][i][j - 1] + grid[i][j]);
98                }
99            }
100        }
101    }
102
103    // The answer is the minimum cost to reach the bottom-right corner using
104    // any number of teleports from 0 to k.
105    let ans = INF;
106    for (let t = 0; t <= k; t++) {
107        ans = Math.min(ans, f[t][rows - 1][cols - 1]);
108    }
109    return ans;
110}
111