class Solution {
public static final int R = 0;
public static final int C = 1;
public static final int W = 2;
public static final int K = 3;
public int minCost(int[][] grid, int t) {
int height = grid.length;
int width = grid[0].length;
int[][] teleport = new int[height * width][3];
int idx = 0;
for (int r = 0; r < height; r += 1) {
for (int c = 0; c < width; c += 1) {
teleport[idx][R] = r;
teleport[idx][C] = c;
teleport[idx][W] = grid[r][c];
idx += 1;
}
}
Arrays.sort(teleport, (a, b) -> a[W] - b[W]);
PriorityQueue<int[]> minWeight = new PriorityQueue<>((a, b) -> a[W] - b[W]);
int[][][] isVisited = new int[height][width][t + 1];
for (int r = 0; r < height; r += 1) {
for (int c = 0; c < width; c += 1) {
Arrays.fill(isVisited[r][c], 1_000_000_000);
}
}
isVisited[0][0][t] = 0;
minWeight.add(new int[]{0, 0, 0, t});
int[] teleIdx = new int[t + 1];
while (!minWeight.isEmpty()) {
int[] curCell = minWeight.poll();
int r = curCell[R];
int c = curCell[C];
int w = curCell[W];
int k = curCell[K];
if (r == height - 1 && c == width - 1) {
return w;
}
if (w > isVisited[r][c][k]) continue;
if (r + 1 < height && w + grid[r + 1][c] < isVisited[r + 1][c][k]) {
isVisited[r + 1][c][k] = w + grid[r + 1][c];
minWeight.add(new int[]{r + 1, c, w + grid[r + 1][c], k});
}
if (c + 1 < width && w + grid[r][c + 1] < isVisited[r][c + 1][k]) {
isVisited[r][c + 1][k] = w + grid[r][c + 1];
minWeight.add(new int[]{r, c + 1, w + grid[r][c + 1], k});
}
if (k > 0) {
while (teleIdx[k] < teleport.length && teleport[teleIdx[k]][W] <= grid[r][c]) {
int[] next = teleport[teleIdx[k]];
if (isVisited[next[R]][next[C]][k - 1] > w) {
isVisited[next[R]][next[C]][k - 1] = w;
minWeight.add(new int[]{next[R], next[C], w, k - 1});
}
teleIdx[k] += 1;
}
}
}
int min = Integer.MAX_VALUE;
for (int i = 0; i <= t; i += 1) {
min = Math.min(min, isVisited[height - 1][width - 1][i]);
}
return min;
}
}
. Thấy gpt gen phát một, nay chắc cheat nhiều. Đề khó hơn hqua mà 3 bài trong 45p còn rank 1k mấy 2k
rank 2k7 cmnr
2000 *2000
