1926. 迷宫中离入口最近的出口

Medium

题目描述

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。

每一步操作，你可以往上，下，左，右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是位于迷宫边界上的 空格子。entrance 格子不算出口。

请你返回从 entrance 到最近出口的最短路径的步数，如果不存在这样的路径，请你返回 -1 。

示例 1：

输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 [1,0]，[0,2] 和 [2,3] 。
一开始，你在入口格子 [1,2] 处。
- 你可以往左移动 2 步到达 [1,0] 。
- 你可以往上移动 1 步到达 [0,2] 。
从入口处没法到达 [2,3] 。
所以，最近的出口是 [0,2] ，距离为 1 步。

示例 2：

输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，位于 [1,2]。
[1,0] 不算出口，因为它是入口格子。
一开始，你在入口格子 [1,0] 处。
- 你可以往右移动 2 步到达 [1,2]。
所以，最近的出口是 [1,2] ，距离为 2 步。

示例 3：

输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。

提示：

maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j] 要么是 '.' ，要么是 '+' 。
entrance.length == 2
0 <= entrancerow < m
0 <= entrancecol < n
entrance 一定是空格子。

解题思路

这道题是典型的最短路径问题，我们需要找到从入口到最近出口的最短距离。

核心思路： 使用**广度优先搜索（BFS）**是最适合的解法，因为BFS能够保证第一次找到出口时就是最短路径。

解题步骤：

初始化队列：将入口位置和步数0加入队列
标记访问：使用访问数组或直接修改原矩阵来避免重复访问
BFS遍历：
- 从队列取出当前位置和步数
- 检查四个方向的相邻格子
- 如果相邻格子是边界上的空格子且不是入口，返回步数+1
- 如果相邻格子是内部空格子且未访问，加入队列继续搜索
边界判断：位置在第一行、最后一行、第一列或最后一列的空格子就是出口

关键点：

出口必须是边界上的空格子，且不能是入口本身
使用BFS确保找到的第一个出口就是最近的
需要避免重复访问同一个格子

时间复杂度分析： 每个格子最多被访问一次，所以时间复杂度为O(m×n)，空间复杂度也是O(m×n)用于存储访问状态。

代码实现

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        queue<pair<int, pair<int, int>>> q; // {steps, {row, col}}
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        q.push({0, {entrance[0], entrance[1]}});
        visited[entrance[0]][entrance[1]] = true;
        
        vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [steps, pos] = q.front();
            auto [row, col] = pos;
            q.pop();
            
            for (auto& dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                    maze[newRow][newCol] == '.' && !visited[newRow][newCol]) {
                    
                    // 检查是否是出口（边界上的空格子且不是入口）
                    if ((newRow == 0 || newRow == m-1 || newCol == 0 || newCol == n-1) &&
                        !(newRow == entrance[0] && newCol == entrance[1])) {
                        return steps + 1;
                    }
                    
                    visited[newRow][newCol] = true;
                    q.push({steps + 1, {newRow, newCol}});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        queue = deque([(entrance[0], entrance[1], 0)])  # (row, col, steps)
        visited = set()
        visited.add((entrance[0], entrance[1]))
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            row, col, steps = queue.popleft()
            
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                
                if (0 <= new_row < m and 0 <= new_col < n and 
                    maze[new_row][new_col] == '.' and (new_row, new_col) not in visited):
                    
                    # 检查是否是出口（边界上的空格子且不是入口）
                    if ((new_row == 0 or new_row == m-1 or new_col == 0 or new_col == n-1) and
                        [new_row, new_col] != entrance):
                        return steps + 1
                    
                    visited.add((new_row, new_col))
                    queue.append((new_row, new_col, steps + 1))
        
        return -1

public class Solution {
    public int NearestExit(char[][] maze, int[] entrance) {
        int m = maze.Length, n = maze[0].Length;
        Queue<(int row, int col, int steps)> queue = new Queue<(int, int, int)>();
        bool[,] visited = new bool[m, n];
        
        queue.Enqueue((entrance[0], entrance[1], 0));
        visited[entrance[0], entrance[1]] = true;
        
        int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (queue.Count > 0) {
            var (row, col, steps) = queue.Dequeue();
            
            for (int i = 0; i < 4; i++) {
                int newRow = row + directions[i, 0];
                int newCol = col + directions[i, 1];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                    maze[newRow][newCol] == '.' && !visited[newRow, newCol]) {
                    
                    // 检查是否是出口（边界上的空格子且不是入口）
                    if ((newRow == 0 || newRow == m-1 || newCol == 0 || newCol == n-1) &&
                        !(newRow == entrance[0] && newCol == entrance[1])) {
                        return steps + 1;
                    }
                    
                    visited[newRow, newCol] = true;
                    queue.Enqueue((newRow, newCol, steps + 1));
                }
            }
        }
        
        return -1;
    }
}

var nearestExit = function(maze, entrance) {
    const m = maze.length;
    const n = maze[0].length;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const queue = [[entrance[0], entrance[1], 0]];
    const visited = new Set();
    visited.add(`${entrance[0]},${entrance[1]}`);
    
    while (queue.length > 0) {
        const [row, col, steps] = queue.shift();
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                maze[newRow][newCol] === '.' && !visited.has(`${newRow},${newCol}`)) {
                
                if (newRow === 0 || newRow === m - 1 || newCol === 0 || newCol === n - 1) {
                    return steps + 1;
                }
                
                visited.add(`${newRow},${newCol}`);
                queue.push([newRow, newCol, steps + 1]);
            }
        }
    }
    
    return -1;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(m × n)	最坏情况下需要遍历迷宫中的每个格子一次
空间复杂度	O(m × n)	需要visited数组记录访问状态，队列最多存储O(m×n)个元素

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析