Skip to content

Instantly share code, notes, and snippets.

@plastic041
Created September 10, 2021 05:43
Show Gist options
  • Save plastic041/7a4953a4e810cc1f1ad16450df19e9cb to your computer and use it in GitHub Desktop.
Save plastic041/7a4953a4e810cc1f1ad16450df19e9cb to your computer and use it in GitHub Desktop.
bfs shortest distance
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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment