LeetCode: Nearest Exit from Entrance in Maze Solution

BFS with a notice

Approach

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 ]
8
9 const [numberOfRows, numberOfCols] = [maze.length, maze[0].length]
10 const [startRow, startCol] = entrance
11 const queue = new MyQueue()
12 maze[startRow][startCol] = "+"
13 queue.enqueue([startRow, startCol, 0])
14
15 let res = -1
16
17 bfs: while (queue.size > 0) {
18 const [currentRow, currentCol, currentDistance] = queue.dequeue()
19
20 for (const [deltaRow, deltaCol] of dirs) {
21 const [nextRow, nextCol, nextDistance] = [
22 currentRow + deltaRow,
23 currentCol + deltaCol,
24 currentDistance + 1,
25 ]
26
27 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 = nextDistance
39 break bfs
40 }
41
42 maze[nextRow][nextCol] = "+"
43 queue.enqueue([nextRow, nextCol, nextDistance])
44 }
45 }
46 }
47
48 return res
49}
50
51class Node {
52 constructor(val, next = null) {
53 this.val = val
54 this.next = next
55 }
56}
57
58class MyQueue {
59 constructor() {
60 this.head = null
61 this.tail = null
62 this.size = 0
63 }
64
65 enqueue(val) {
66 const node = new Node(val)
67
68 this.size++
69
70 if (!this.tail) {
71 this.head = this.tail = node
72 return
73 }
74
75 this.tail.next = node
76 this.tail = this.tail.next
77 }
78
79 dequeue() {
80 if (!this.head) return null
81
82 const node = this.head
83 this.size--
84 this.head = this.head.next
85
86 if (!this.head) this.tail = null
87
88 return node.val
89 }
90
91 peek() {
92 if (!this.head) return null
93
94 return this.head.val
95 }
96}

References

Original problem

Comments

Loading comments...

Tags

leetcode

bfs

Next Post

Advent of Code 2022 - Day 3: Rucksack Reorganization

Dec 3, 2022

Find shared item and calculate

Previous Post

LeetCode: Min Stack

Nov 15, 2022

Linked list in action

HoningJS

Search Posts