迷宫中离入口最近的出口 (Nearest Exit from Entrance in Maze)

1. 题目描述

题目背景： 在迷宫搜索类题目中，寻找“最短路径”是核心考点。本题要求在一个给定的二维网格迷宫中，找到从起点出发到达任意一个“出口”的最少步数。

任务描述： 给你一个 $m \times n$ 的迷宫网格 maze（下标从 $0$ 开始），网格中有空格（用 . 表示）和墙（用 + 表示）。同时给你入口的坐标 entrance = [r0, c0]。

你在迷宫中每一步可以向 上、下、左、右 移动一个空格。你不能进入墙所在的格子，也不能移动到迷宫边界之外。

出口 的定义是：位于迷宫 边界（第一行、最后一行、第一列、最后一列）的 空格，且该空格 不能是入口本身。

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

输入格式：

1. 第一行包含两个整数 $m$ 和 $n$ ($1 \le m, n \le 100$)，表示迷宫的行数和列数。
2. 接下来的 $m$ 行，每行包含一个长度为 $n$ 的字符串，表示迷宫的布局。
3. 最后一行包含两个整数 $r_0$ 和 $c_0$，表示入口的行坐标和列坐标。

输出格式： 一个整数，表示最短步数或 -1。

---

样例 1： 输入：

3 3
++.
...
+++
1 2

输出：

1

(解释：入口是 {1, 2}。最近出口是 {0, 2}，只需 1 步。)

样例 2： 输入：

3 3
+++
...
+++
1 0

输出：

2

(解释：入口是 {1, 0}。出口有 {1, 2}，需 2 步。)

样例 3： 输入：

1 2
.+
0 0

输出：

-1

(解释：入口是 {0, 0}。虽然它在边界上，但它是入口，不能作为出口。)

---

2. 预备知识点

1. 宽度优先搜索 (BFS)：在无权图（或等权网格）中寻找最短路径的标准算法。
2. 二维数组遍历：使用方向数组 dx[] = {-1, 1, 0, 0} 和 dy[] = {0, 0, -1, 1} 简化四方向移动。
3. 队列 (Queue)：BFS 的核心数据结构，维护“先发现先搜索”的顺序。
4. 状态标记：使用 visited 数组或直接修改原地图标记已访问节点，防止死循环。

---

3. 启发式思维引导

请拿出草稿纸，跟随教练的思路，一步步写出推导过程。

第一步：寻找问题的“扩散性”

想象你在入口点滴了一滴墨水，墨水会每秒向相邻的空格扩散一格。

• 思考：第一秒扩散到的位置距离入口是几？第二秒呢？
• 结论：这种层层扩散的特性，完美对应了 BFS。

第二步：定义“出口”判定条件

在代码逻辑中，如何判断当前位置 (r, c) 是出口？

• 条件 A：它必须在边界上，即 r == 0 或 r == m-1 或 c == 0 或 c == n-1。
• 条件 B：它必须是空格 .。
• 条件 C：它不能是入口 (r0, c0)。

第三步：防止“鬼打墙”

• 问题：如果搜索时走回了已经走过的路怎么办？
• 对策：建立一个布尔数组 vis[m][n]。每当一个点进入队列时，立刻标记 vis[r][c] = true。

第四步：复杂度分析（在草稿纸上估算）

• 时间复杂度：每个格子最多进出队列一次。迷宫最大为 $100 \times 100 = 10000$ 个格子。每个格子检查 4 个方向。总复杂度 $O(M \times N)$。
• 空间复杂度：需要队列存储节点和 vis 数组。总空间 $O(M \times N)$。

---

4. 算法流程图 (C++14 逻辑提示)

为了遵循 Mermaid 语法，特殊字符已使用描述性文字替换。

graph TD
    Start(开始) --> Init[初始化队列 Q 和 vis 标记数组]
    Init --> PushStart[将入口坐标入队并标记已访问]
    PushStart --> StepInit[初始化步数 step 为 0]
    
    StepInit --> WhileQ{队列是否不为空}
    WhileQ -- 否 --> ReturnFail(返回 -1)
    
    WhileQ -- 是 --> GetSize(获取当前队列长度 sz)
    GetSize --> ForLoop{循环 sz 次}
    
    ForLoop -- 迭代 --> PopNode(弹出队首坐标 curr)
    PopNode --> DirLoop(尝试四个方向移动到新坐标 next)
    
    DirLoop -- 有效移动 --> CheckExit{next 是出口吗}
    CheckExit -- 是 --> ReturnAns(输出 step + 1)
    CheckExit -- 否 --> MarkAndPush(标记 next 已访问并入队)
    MarkAndPush --> DirLoop
    
    DirLoop -- 所有方向试完 --> ForLoop
    ForLoop -- 循环结束 --> StepInc(步数 step 增加 1)
    StepInc --> WhileQ

---

5. 读题关键词总结

在 NOI 竞赛读题时，看到以下词汇要迅速反应：

1. “最短步数” (Shortest path/Minimum steps)：
   • 核心算法：BFS（优先选择），除非边有权值（则用 Dijkstra）。
2. “上下左右移动” (Grid traversal)：
   • 技巧：准备好方向数组。
3. “边界” (Boundary)：
   • 注意点：判定条件通常是 r == 0 || r == m-1 || c == 0 || c == n-1。
4. “不能是入口本身”：
   • 警示：这是本题唯一的坑点，必须在判断出口逻辑中增加 !(nx == r0 && ny == c0)。

教练点评： 本题是经典的 BFS 迷宫模板题。在 NOI 考场上，这种题目要求“一次性写对”。注意队列中存储的是坐标（通常使用 std::pair<int, int> 或结构体），并且入队时就要标记已访问，否则会导致同一个点多次入队，造成 Memory Limit Exceeded 或 Time Limit Exceeded。加油！