Answer:

  1. From any one position, there are eight directions you can go, one step at a time. However, there is no need to go up, left and left, because there is no scene where you need to go back to bypass the obstacle. You just need to keep going down to the right.
  2. With BFS, each loop starts with the current layer node and diffuses down and right to the next layer node. Increase the number of steps (path length) taken one level at a time by 1.
  3. When the end point is encountered, the shortest path is found, and the number of layers is the length of the path.
/ * * *@param {number[][]} grid
 * @return {number}* /
var shortestPathBinaryMatrix = function (grid) {
  // The end position of the cache matrix
  const m = grid.length - 1;
  const n = grid[0].length - 1;

  // When the starting point and the ending point are 1, we cannot reach the end point
  if (grid[0] [0= = =1 || grid[m][n] === 1) {
    return -1;
  }

  // If the matrix has only one point and is 0, the path is 1
  if (m === 0 && n === 0 && grid[0] [0= = =0) {
    return 1;
  }

  let queue = [[0.0]].// Use queues for BFS searches
  let level = 1; // Cache path length. The starting point is 1
  // Can walk in all directions, cache 8 directions
  const direction = [
    [-1.1]./ / right
    [0.1]./ / right
    [1.1]./ / right
    [1.0]./ /
    [1, -1]./ / lower left
    // All three of them are backwards. no judgment required
    // [-1, 0], // up
    // [0, -1], // left
    // [-1, -1], // upper left
  ];

  // If there is a value in the queue, the search continues
  while (queue.length) {
    // Cache the number of nodes in the current layer
    let queueLength = queue.length;

    // Only the nodes of the current layer are traversed at a time
    while (--queueLength >= 0) {
      // Assign a coordinate and calculate the next position where it can walk
      const [x, y] = queue.shift();

      for (let i = 0; i < direction.length; i++) {
        // The next step is to walk around and calculate the corresponding new coordinates
        const newX = x + direction[i][0];
        const newY = y + direction[i][1];

        // If the new coordinate is outside the grid, or is marked as 1, indicating that it cannot walk, then skip
        if (
          newX < 0 ||
          newY < 0 ||
          newX > m ||
          newY > m ||
          grid[newX][newY] === 1
        ) {
          continue;
        }

        // If the new coordinate is the destination, it means that the path is found
        if (newX === m && newY === n) {
          return level + 1;
        }
        // Mark the location of the walk as 1 to avoid repeated walks
        grid[newX][newY] = 1;
        // Queue the next coordinates for the next loop
        queue.push([newX, newY]);
      }
    }

    level++; // For each step forward, increase the number of steps by 1
  }

  return -1;
};
Copy the code