1
/**
2
 * @param {number[][]} grid
3
 * @return {number}
4
 */
5
var shortestPathBinaryMatrix = function (grid) {
6
  const n = grid.length;
7
  const directions = [
8
    [-1, 0],
9
    [-1, 1],
10
    [0, 1],
11
    [1, 1],
12
    [1, 0],
13
    [1, -1],
14
    [0, -1],
15
    [-1, -1],
16
  ];
17
  const visited = [];
18
  const distance = [];
19
  const predecessor = [];
20
  const queue = [];
21

22
  for (let i = 0; i < n; i++) {
23
    visited.push(Array.from({ length: n }, (v, i) => false));
24
    distance.push(Array.from({ length: n }, (v, i) => 9999));
25
    predecessor.push(Array.from({ length: n }, (v, i) => null));
26
  }
27

28
  const startIndex = [0, 0];
29
  if (grid[startIndex[0]][startIndex[1]] !== 0) {
30
    return -1;
31
  }
32

33
  queue.push(startIndex);
34
  distance[startIndex[0]][startIndex[1]] = 1;
35

36
  while (queue.length > 0) {
37
    const current = queue.shift();
38
    visited[current[0]][current[1]] = true;
39

40
    if (current[0] === n - 1 && current[1] === n - 1) {
41
      break;
42
    }
43

44
    directions.forEach((dir) => {
45
      const x = current[0] + dir[0];
46
      const y = current[1] + dir[1];
47

48
      if (x < 0 || y < 0 || x >= n || y >= n) {
49
        return;
50
      }
51

52
      if (
53
        grid[x][y] === 0 &&
54
        visited[x][y] === false &&
55
        distance[x][y] > distance[current[0]][current[1]] + 1
56
      ) {
57
        distance[x][y] = distance[current[0]][current[1]] + 1;
58
        predecessor[x][y] = current;
59
        queue.push([x, y]);
60
      }
61
    });
62
  }
63

64
  console.log(distance);
65
  console.log(visited);
66
  console.log(predecessor);
67

68
  return distance[n - 1][n - 1] >= 999 ? -1 : distance[n - 1][n - 1];
69
};