Solution1293.java

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;
            }
        }
    }
}