1091. Shortest Path in Binary Matrix

leetcode_1091.md

Description

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner). The length of a clear path is the number of visited cells of this path.

Link to the original problem

Example 1

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

Idea

1. This is a fairly simple question, comparing to the one with obstacles.
2. The difference is that we have no obstacles and we can move in 8 directions.
3. Does that change the logic though? Actually, not much.
4. Imagine we are standing on one of the cells, how do we proceed?
5. Because we're trying to find a clear path, so if the cell has a 1, we ignore that direction.
6. How do we calculate the solution? We still need some kind of state to remember our progress.
7. So we definitely need the coordinates (x, y). There's no obstacles, so that simplifies it a bit.
8. We can still have a separate array to record our current minimum steps to get to current cell. However, if you think about it, we did that only because there're obstacles and we might need to revisit some cells based on if we remove the (previous) obstacles and the order of removing it also might change the path.
9. Here we don't need to revisit a cell, why?
10. Because when we revisit a cell, that means we had a shorter path that led us to this cell, right? In that case, it wouldn't be shorter than the previous path.
11. So we can add current steps to the state and make it (x, y, current steps) and then apply BFS pattern and move "forward", until we reach the destination.
12. A simple trick is to mark visited cells as 1, so when we do BFS we won't revisit the cells.
13. The code should explain itself.

Solution

Javascript

const shortestPathBinaryMatrix = function(grid) {  
  if (grid[0][0] == 1) return -1;
 
  const dirs = [[1, 1], [1, 0], [1, -1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [0, 1]];
  const N = grid.length;
  const isValid = (x, y) => x >= 0 && x < N && y >= 0 && y < N;
  
  grid[0][0] = 1;
  const queue = [[0, 0, 1]]; // [[x,y,steps]]
  while (queue.length) {
    const [x, y, dist] = queue.shift();
    if (x == N - 1 && y == N - 1) return dist;
    
    for (const [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (isValid(nx, ny) && grid[nx][ny] == 0) {
        queue.push([nx, ny, dist + 1]);
        grid[nx][ny] = 1;
      }
    }
  }
  return -1;
};