Created
January 2, 2023 11:24
-
-
Save jutikorn/6449b3f03fcc491710fbaf597a09c7b3 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
private static final int[][] directions = new int[][] { | |
{0, 1}, | |
{1, 0}, | |
{-1, 0}, | |
{0, -1} | |
}; | |
public int shortestPath(int[][] grid, int k) { | |
int TARGET_ROW = grid.length -1; | |
int TARGET_COL = grid[0].length -1; | |
// row, col, steps, k | |
PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>( | |
(n1, n2) -> n1[2] - n2[2] | |
); | |
// row, col, steps, k | |
minHeap.add(new int[]{0, 0, 0, k}); | |
int res = -1; | |
while(!minHeap.isEmpty()) { | |
int[] points = minHeap.poll(); | |
int row = points[0]; | |
int col = points[1]; | |
int steps = points[2]; | |
int kVal = points[3] - grid[row][col]; | |
grid[row][col] = 2; | |
if(kVal < 0) continue; | |
if(TARGET_ROW == row && TARGET_COL == col) { | |
res = steps; | |
break; | |
} | |
for(int[] dir: directions) { | |
int newRow = row + dir[0]; | |
int newCol = col + dir[1]; | |
if(isInBound(grid, newRow, newCol) && grid[newRow][newCol] != 2) { | |
minHeap.add(new int[]{newRow, newCol, steps+1, kVal}); | |
} | |
} | |
} | |
return res; | |
} | |
private boolean isInBound(int[][] grid, int row, int col) { | |
return row >= 0 && col >= 0 && row < grid.length && col < grid[row].length; | |
} | |
class PointComparator implements Comparator<int[]> { | |
@Override | |
public int compare(int[] o1, int[] o2) { | |
int step1 = o1[2]; | |
int step2 = o2[2]; | |
int k1 = o1[3]; | |
int k2 = o2[3]; | |
if(step1 == step2) { | |
return k2 -k1; | |
} else { | |
return step1 - step2; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment