bfs shortest distance

bfsShortestDistance.ts

const bfsDistance = (
  array: number[][],
  start: number[],
  end: number[]
): number => {
  const visited = new Set();
  const queue: Point[] = [];
  let distance = 0;

  const startPoint: Point = { x: start[0], y: start[1] };
  const endPoint: Point = { x: end[0], y: end[1] };
  visited.add(pointToString(startPoint));
  queue.push(startPoint);

  while (queue) {
    distance += 1;
    const currentPoint = queue.shift();
    if (currentPoint) {
      visited.add(pointToString(currentPoint));
      const neighbors = getNeighbors(currentPoint).filter((point) => {
        return isValid(array, point) && !visited.has(pointToString(point));
      });
      for (const neighborPoint of neighbors) {
        const isEqual = isPointEqual(neighborPoint, endPoint);
        if (isEqual) {
          return distance;
        }
        queue.push(neighborPoint);
      }
    }
  }
  return -1;
};

type Point = {
  x: number;
  y: number;
};

const isPointEqual = (point1: Point, point2: Point) =>
  point1.x === point2.x && point1.y === point2.y;

const getNeighbors = (point: Point) => {
  const up: Point = { x: point.x, y: point.y - 1 };
  const down: Point = { x: point.x, y: point.y + 1 };
  const left: Point = { x: point.x - 1, y: point.y };
  const right: Point = { x: point.x + 1, y: point.y };

  return [up, right, down, left];
};

const isValid = (array: number[][], point: Point) => {
  if (array[point.y]) {
    if (array[point.y][point.x]) {
      return true;
    }
  }
  return false;
};

const pointToString = (point: Point) => {
  return `${point.x}${point.y}`;
};


// test
const array = [
  [1, 0, 0],
  [1, 1, 1],
  [0, 0, 1],
];

const result = bfsDistance(array, [0, 0], [2, 2]);
console.log(result);