shortestpath.java

class shortestPath {
    int m, n;
    public int shortestPath(int[][] grid, int k) {
        m = grid.length;
        n = grid[0].length;

        Integer[][][] dp = new Integer[m][n][k + 1];
        boolean[][][] isVisited = new boolean[m][n][k + 1];

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        int ans = path(grid, k, m - 1, n - 1, isVisited, dp);
        return (ans >= m * n) ? -1 : ans; // max number of steps can be m*n
    }
    public int path(int[][] grid, int k, int i, int j, boolean[][][] isVisited, Integer[][][] dp){
        if(i < 0 || j < 0 || i >= m || j >= n || isVisited[i][j][k]){
            return (int)1e9;
        }

        if(dp[i][j][k] != -1){
            return dp[i][j][k];
        }

        if(i == 0 && j == 0){
            return dp[i][j][k] = 0;
        }

        if(grid[i][j] == 1){
            if(k == 0){
                return dp[i][j][k] = (int)1e9;
            }
            k--;
        }

        isVisited[i][j][k] = true;
        // up
        int up = 1 + path(grid, k, i - 1, j, isVisited, dp);

        // left
        int left = 1 + path(grid, k, i, j - 1, isVisited, dp);

        // down
        int down = 1 + path(grid, k, i + 1, j, isVisited, dp);

        // right
        int right = 1 + path(grid, k, i, j + 1, isVisited, dp);

        isVisited[i][j][k] = false;
        return dp[i][j][k] = Math.min(up, Math.min(left, Math.min(right, down)));
    }
}