Nearest Exit from Entrance in Maze

題目描述

給定一個 m×n 的迷宮（. 是空格，+ 是牆），和入口座標 entrance。找到離入口最近的出口（邊界上的空格，且不是入口本身）。回傳最少步數，如果沒有出口回傳 -1。

輸入: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]]
      entrance = [1,2]
輸出: 1
解釋: (1,2) 往上走一步到 (0,2) 就是邊界出口

輸入: maze = [["+","+","+"],[".",".","."],["+","+","+"]]
      entrance = [1,0]
輸出: 2

解題思路

BFS 初始化

入口放入 Queue，標記為已訪問

四方向擴展

每步嘗試上下左右四個方向

檢查出口

如果到達邊界空格且不是入口，回傳步數

繼續搜尋

不是出口就加入 Queue，繼續下一步

無解

Queue 為空仍未找到，回傳 -1

程式碼

C#

csharp

public class Solution {
    public int NearestExit(char[][] maze, int[] entrance) {
        int m = maze.Length, n = maze[0].Length;
        var queue = new Queue<(int r, int c)>();
        queue.Enqueue((entrance[0], entrance[1]));
        maze[entrance[0]][entrance[1]] = '+'; // 標記已訪問
 
        int[][] dirs = { new[]{0,1}, new[]{0,-1}, new[]{1,0}, new[]{-1,0} };
        int steps = 0;
 
        while (queue.Count > 0) {
            steps++;
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                var (r, c) = queue.Dequeue();
                foreach (var d in dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    if (maze[nr][nc] == '+') continue;
 
                    // 是否為邊界出口
                    if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) {
                        return steps;
                    }
                    maze[nr][nc] = '+'; // 標記已訪問
                    queue.Enqueue((nr, nc));
                }
            }
        }
        return -1;
    }
}

TypeScript

typescript

function nearestExit(maze: string[][], entrance: number[]): number {
    const m = maze.length, n = maze[0].length;
    const queue: [number, number][] = [[entrance[0], entrance[1]]];
    maze[entrance[0]][entrance[1]] = "+"; // 標記已訪問
 
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    let steps = 0;
 
    while (queue.length > 0) {
        steps++;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const [r, c] = queue.shift()!;
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (maze[nr][nc] === "+") continue;
 
                if (nr === 0 || nr === m - 1 || nc === 0 || nc === n - 1) {
                    return steps;
                }
                maze[nr][nc] = "+";
                queue.push([nr, nc]);
            }
        }
    }
    return -1;
}

Python

python

from collections import deque
 
def nearestExit(maze: list[list[str]], entrance: list[int]) -> int:
    m, n = len(maze), len(maze[0])
    queue = deque([(entrance[0], entrance[1])])
    maze[entrance[0]][entrance[1]] = '+'  # 標記已訪問
 
    steps = 0
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
 
    while queue:
        steps += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue
                if maze[nr][nc] == '+':
                    continue
 
                if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
                    return steps
                maze[nr][nc] = '+'
                queue.append((nr, nc))
 
    return -1

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(m × n) | O(m × n) |

圖解

入口 (1,2)

往上→

步驟 1: (0,2)

在邊界上→

邊界出口！

進階觀點

💡面試追問

為什麼 BFS 保證最短？ BFS 按步數逐層擴展，第一次到達的出口一定是步數最少的。DFS 不保證最短。

修改原陣列 vs 額外 visited：這題直接把走過的格子改成 + 來標記已訪問，省了額外空間。但面試中要說明這會修改輸入。

變體題：LC 994 Rotting Oranges（多源 BFS）、LC 1091 Shortest Path in Binary Matrix。

理解測驗

🤔 為什麼入口不能當作出口？

🤔 如果用 DFS 代替 BFS，結果會怎樣？