# 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var 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] = entrance11  const queue = new MyQueue()12  maze[startRow][startCol] = "+"13  queue.enqueue([startRow, startCol, 0])14
15  let res = -116
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 = nextDistance39          break bfs40        }41
42        maze[nextRow][nextCol] = "+"43        queue.enqueue([nextRow, nextCol, nextDistance])44      }45    }46  }47
48  return res49}50
51class Node {52  constructor(val, next = null) {53    this.val = val54    this.next = next55  }56}57
58class MyQueue {59  constructor() {60    this.head = null61    this.tail = null62    this.size = 063  }64
65  enqueue(val) {66    const node = new Node(val)67
68    this.size++69
70    if (!this.tail) {71      this.head = this.tail = node72      return73    }74
75    this.tail.next = node76    this.tail = this.tail.next77  }78
79  dequeue() {80    if (!this.head) return null81
86    if (!this.head) this.tail = null87
88    return node.val89  }90
91  peek() {92    if (!this.head) return null93

Original problem

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