1
class Solution {
2
 public:
3
  vector<vector<int>> directions{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
4
  int shortestPath(vector<vector<int>> &grid, int k) {
5
    int m = grid.size(), n = grid[0].size(), ans = 0;
6
    queue<vector<int>> q;
7
    bool visited[m][n][k + 1];
8
    memset(visited, false, sizeof(visited));
9
    q.push({0, 0, k});
10
    visited[0][0][k] = true;
11

12
    while (!q.empty()) {
13
      int size = q.size();
14
      while (size--) {
15
        auto p = q.front();
16
        q.pop();
17

18
        if (p[0] == m - 1 && p[1] == n - 1) return ans;
19
        for (auto x : directions) {
20
          int i = p[0] + x[0];
21
          int j = p[1] + x[1];
22
          int obstacle = p[2];
23

24
          if (i >= 0 && i < m && j >= 0 && j < n) {
25
            if (grid[i][j] == 0 && !visited[i][j][obstacle]) {
26
              q.push({i, j, obstacle});
27
              visited[i][j][obstacle] = true;
28
            } else if (grid[i][j] == 1 && obstacle > 0 && !visited[i][j][obstacle - 1]) {
29
              q.push({i, j, obstacle - 1});
30
              visited[i][j][obstacle - 1] = true;
31
            }
32
          }
33
        }
34
      }
35
      ans++;
36
    }
37
    return -1;
38
  }
39
};