1926. Nearest Exit from Entrance in Maze

Leetcode link

题目简介

/**
 * @param {character[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */

题目给我们一个二维数组 maze 以及一个数组 entrance

maze 元素有两种 . 代表可以走的路、+ 代表不能走的墙

entrance 代表我们一开始在 maze 中的位置

题目要求我们计算从 entrance 到 maze 的边缘最少需要用到几步（起始位置在边缘的话不算）

解题思路

这题的思路是运用图的 BFS 来做

具体思路就是，我们每次都从当前位置的上下左右四个方向出发，直到第一个遇到边缘就返回当前的步数

为了减少不必要的计算，我们可以使用 visited 数组来记录已经遍历过的位置

Javascript

/**
 * @param {character[][]} maze
 * @param {number[]} entrance
 * @return {number}
 */
var nearestExit = function(maze, entrance) {
    const height = maze.length
    const width = maze[0].length
    const visited = Array.from({length: height}, _ => Array(width).fill(false))
    visited[entrance[0]][entrance[1]] = true
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    // [positionRow, poitionColumn, steps]
    const queue = [[...entrance, 0]]

    while(queue.length > 0) {
        const [row, col, steps] = queue.shift()

        if((row === 0 || row === height-1 || col === 0 || col === width-1) && steps > 0) {
            // the shortest path will reach here first
            return steps
        }

        for(const [dr, dc] of dirs) {
            const newRow = row + dr
            const newCol = col + dc

            if(newRow < 0 || newRow >= height || newCol < 0 || newCol >= width || visited[newRow][newCol] || maze[newRow][newCol] === '+') {
                continue
            }

            visited[newRow][newCol] = true
            queue.push([newRow, newCol, steps+1])
        }
    }

    return -1
};

复杂度分析

m 代表 maze 的宽

n 代表 maze 的高

时间

最坏的情况我们需要把所有的 maze 元素入栈（复杂度 O(mn)）+每个入栈元素需要进行四个方向查找（复杂度 O(4mn)）

所以加起来是 O(mn)

空间

主要来源于 visited 的空间占用以及栈的空间占用，所以是 O(mn)