LeetCode: Nearest Exit from Entrance in Maze Solution
BFS with a noticeApproach
BFS will guarantee the nearest exit on the first valid
Mark a coordinate as visited before pusing to the queue. This is important, as it would avoid duplication, which will lead to TLE or MLE.
Implementation
1var nearestExit = function (maze, entrance) {2 const dirs = [3 [-1, 0],4 [1, 0],5 [0, 1],6 [0, -1],7 ]89 const [numberOfRows, numberOfCols] = [maze.length, maze[0].length]10 const [startRow, startCol] = entrance11 const queue = new MyQueue()12 maze[startRow][startCol] = "+"13 queue.enqueue([startRow, startCol, 0])1415 let res = -11617 bfs: while (queue.size > 0) {18 const [currentRow, currentCol, currentDistance] = queue.dequeue()1920 for (const [deltaRow, deltaCol] of dirs) {21 const [nextRow, nextCol, nextDistance] = [22 currentRow + deltaRow,23 currentCol + deltaCol,24 currentDistance + 1,25 ]2627 if (28 0 <= nextRow &&29 nextRow < numberOfRows &&30 0 <= nextCol &&31 nextCol < numberOfCols &&32 maze[nextRow][nextCol] === "."33 ) {34 if (35 [0, numberOfRows - 1].includes(nextRow) ||36 [0, numberOfCols - 1].includes(nextCol)37 ) {38 res = nextDistance39 break bfs40 }4142 maze[nextRow][nextCol] = "+"43 queue.enqueue([nextRow, nextCol, nextDistance])44 }45 }46 }4748 return res49}5051class Node {52 constructor(val, next = null) {53 this.val = val54 this.next = next55 }56}5758class MyQueue {59 constructor() {60 this.head = null61 this.tail = null62 this.size = 063 }6465 enqueue(val) {66 const node = new Node(val)6768 this.size++6970 if (!this.tail) {71 this.head = this.tail = node72 return73 }7475 this.tail.next = node76 this.tail = this.tail.next77 }7879 dequeue() {80 if (!this.head) return null8182 const node = this.head83 this.size--84 this.head = this.head.next8586 if (!this.head) this.tail = null8788 return node.val89 }9091 peek() {92 if (!this.head) return null9394 return this.head.val95 }96}
References
Comments
Loading comments...
Tags
leetcode
bfs
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.