1
class Solution {
2
  int rowLen = 0;
3
  int colLen = 0;
4
  int MAXVAL = 0;
5

6
  public int shortestPath(int[][] grid, int k) {
7
    rowLen = grid.length;
8
    colLen = grid[0].length;
9
    MAXVAL = rowLen * colLen + 1;
10
    int path =
11
        shortest(
12
            grid, k, 0, 0, 0, new boolean[rowLen][colLen], new Integer[rowLen][colLen][k + 1][4]);
13
    return path == MAXVAL ? -1 : path;
14
  }
15

16
  /* Direction
17
  0 - Up
18
  1 - Down
19
  2 - Left
20
  3 - Right
21
  */
22

23
  // For each cell(row, col) explore all possible ways to reach it with minimum cost, hence we
24
  // consider the direction as well
25
  int shortest(
26
      int[][] grid,
27
      int k,
28
      int row,
29
      int col,
30
      int direction,
31
      boolean[][] visited,
32
      Integer[][][][] dp) {
33
    // Reached end of the matrix
34
    if (row == rowLen - 1 && col == colLen - 1 && k >= 0) return 0;
35

36
    // Couldn't find a valid path
37
    if (k < 0 || row < 0 || col < 0 || row >= rowLen || col >= colLen) return MAXVAL;
38

39
    if (dp[row][col][k][direction] != null) return dp[row][col][k][direction];
40

41
    // 4 options to choose a direction
42
    // Go right
43
    int op1 = MAXVAL;
44
    if (col + 1 < colLen && !visited[row][col + 1]) {
45
      visited[row][col + 1] = true;
46
      if (grid[row][col + 1] == 0) op1 = shortest(grid, k, row, col + 1, 3, visited, dp) + 1;
47
      else op1 = shortest(grid, k - 1, row, col + 1, 3, visited, dp) + 1;
48
      visited[row][col + 1] = false;
49
    }
50

51
    // Go left
52
    int op2 = MAXVAL;
53
    if (col - 1 >= 0 && !visited[row][col - 1]) {
54
      visited[row][col - 1] = true;
55
      if (grid[row][col - 1] == 0) op2 = shortest(grid, k, row, col - 1, 2, visited, dp) + 1;
56
      else op2 = shortest(grid, k - 1, row, col - 1, 2, visited, dp) + 1;
57
      visited[row][col - 1] = false;
58
    }
59

60
    // Go up
61
    int op3 = MAXVAL;
62
    if (row - 1 >= 0 && !visited[row - 1][col]) {
63
      visited[row - 1][col] = true;
64
      if (grid[row - 1][col] == 0) op3 = shortest(grid, k, row - 1, col, 0, visited, dp) + 1;
65
      else op3 = shortest(grid, k - 1, row - 1, col, 0, visited, dp) + 1;
66
      visited[row - 1][col] = false;
67
    }
68

69
    // Go down
70
    int op4 = MAXVAL;
71
    if (row + 1 < rowLen && !visited[row + 1][col]) {
72
      visited[row + 1][col] = true;
73
      if (grid[row + 1][col] == 0) op4 = shortest(grid, k, row + 1, col, 1, visited, dp) + 1;
74
      else op4 = shortest(grid, k - 1, row + 1, col, 1, visited, dp) + 1;
75
      visited[row + 1][col] = false;
76
    }
77

78
    dp[row][col][k][direction] = Math.min(Math.min(op1, op2), Math.min(op3, op4));
79
    return dp[row][col][k][direction];
80
  }
81
}