1091. Shortest Path in Binary Matrix

shortest-path-binary-matrix.ts

function shortestPathBinaryMatrix(grid: number[][]): number {
  const getDirections = ([row, col]: [number, number]): number[][] => {
    const canMove = ([row, col]: [number, number]) => {
      return (row >= 0 && row < grid.length) && (col >= 0 && col < grid[row].length)
    }

    // Given a 3x3 matrix with row/col index of [1,1]
    // we should return:
    //
    // [0, 1] == North
    // [2, 1] == South
    // [1, 0] == East
    // [0, 1] == West
    // [0, 0] == North west
    // [2, 1] == South west
    // [2, 2] == South east
    // [0, 2] == North east
    //
    //    0  1  2
    // 0 [0, 0, 0]
    // 1 [0, *, 0]
    // 2 [0, 0, 0]
    const movements = [
      // North West
      [-1, -1],
      // North east
      [-1, 1],
      // North
      [-1, 0],
      // South
      [1, 0],
      // South west
      [1, -1],
      // South east
      [1, 1],
      // West
      [0, -1],
      // East
      [0, 1]
    ]

    return movements.reduce<number[][]>((directions, [rowMovement, colMovement]) => {
      const direction: [number, number] = [row + rowMovement, col + colMovement];

      if (canMove(direction)) {
        directions.push(direction);
      }

      return directions;
    }, []);
  }

  const bfs = (startingPoint: [number, number]): number => {
    const isDestination = ([row, col]: [number, number]) => {
      return (row === grid.length -1) && (col === grid[row].length - 1);
    }
    const visited: boolean[][] = grid.map(row => row.map(col => false));

    // row,col,length
    const queue: [number, number, number][] = [];

    queue.push([...startingPoint, 1]);

    while (queue.length) {
      const current = queue.shift();

      if (!current) {
        throw new Error('Queue::Shift() should never return undefined');
      }

      const [row, col, length] = current;

      if (grid[row][col] === 1 || visited[row][col]) {
        continue;
      } else {
        visited[row][col] = true;
      }

      if (isDestination([row, col])) {
        return length;
      }

      const nextPoints = getDirections([row, col]);

      nextPoints.forEach(([row, col]) => {
        queue.push([row, col, length + 1]);
      });
    }

    return -1;
  }

  return bfs([0, 0]);
};