1
var shortestPath = function (grid, k) {
2
  const dir = [
3
    [-1, 0],
4
    [1, 0],
5
    [0, -1],
6
    [0, 1],
7
  ];
8
  const m = grid.length;
9
  const n = grid[0].length;
10

11
  let q = [[0, 0, k]];
12
  const visited = new Set();
13
  visited.add(`0:0:${k}`);
14
  let cnt = 0;
15
  while (q.length > 0) {
16
    const size = q.length;
17
    for (let i = 0; i < size; i++) {
18
      let [x, y, ob] = q.shift();
19
      if (x === m - 1 && y === n - 1) {
20
        return cnt;
21
      }
22
      for (const d of dir) {
23
        const xx = d[0] + x;
24
        const yy = d[1] + y;
25
        if (xx >= 0 && xx < m && yy >= 0 && yy < n) {
26
          const newK = grid[xx][yy] === 1 ? ob - 1 : ob;
27
          if (newK >= 0 && !visited.has(`${xx}:${yy}:${newK}`)) {
28
            q.push([xx, yy, newK]);
29
            visited.add(`${xx}:${yy}:${newK}`);
30
          }
31
        }
32
      }
33
    }
34
    cnt++;
35
  }
36
  return -1;
37
};