Created
September 10, 2021 05:43
-
-
Save plastic041/7a4953a4e810cc1f1ad16450df19e9cb to your computer and use it in GitHub Desktop.
bfs shortest distance
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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