迷宫中离入口最近的出口 图解题解

这道题到底在问什么

输入

maze=["++.+","...+","+++."], entrance=[1,2]

输出

1(相邻就有边界出口)

最优解：一步一步想明白

1. 3记住「从入口一圈圈扩、入队即标记、第一次踩到边界空地即最近出口」,下面逐帧套它。
2. 4入口 (1,1)(紫)入队,步数 0,并标记为已访问(以后不再走它)。规则:出口必须是边界上的空地、且不能是入口本身。开始一圈圈往外扩。
3. 5弹出队首 (1,1)(紫,步数 0)。看它上下左右四个方向,能走的空地准备入队。
4. 6把能走的新空地 (2,1)、(1,2)(高亮)标记已访问、带步数 1 入队。(1,1) 处理完转蓝。
5. 7弹出队首 (2,1)(紫,步数 1)。看它上下左右四个方向,能走的空地准备入队。
6. 8把能走的新空地 (3,1)、(2,2)(高亮)标记已访问、带步数 2 入队。(2,1) 处理完转蓝。
7. 9弹出队首 (1,2)(紫,步数 1)。看它上下左右四个方向,能走的空地准备入队。
8. 10把能走的新空地 (1,3)(高亮)标记已访问、带步数 2 入队。(1,2) 处理完转蓝。
9. 11弹出队首 (3,1)(紫,步数 2)。看它上下左右四个方向,能走的空地准备入队。
10. 12把能走的新空地 (3,2)(高亮)标记已访问、带步数 3 入队。(3,1) 处理完转蓝。
11. 13弹出队首 (2,2)(紫,步数 2)。看它上下左右四个方向,能走的空地准备入队。
12. 14把能走的新空地 (2,3)(高亮)标记已访问、带步数 3 入队。(2,2) 处理完转蓝。
13. 15弹出队首 (1,3)(紫,步数 2)。看它上下左右四个方向,能走的空地准备入队。
14. 16把能走的新空地 (1,4)(高亮)标记已访问、带步数 3 入队。(1,3) 处理完转蓝。
15. 17弹出队首 (3,2)(紫,步数 3)。看它上下左右四个方向,能走的空地准备入队。
16. 18把能走的新空地 (3,3)(高亮)标记已访问、带步数 4 入队。(3,2) 处理完转蓝。
17. 19弹出队首 (2,3)(紫,步数 3)。看它上下左右四个方向,能走的空地准备入队。
18. 20把能走的新空地 (2,4)(高亮)标记已访问、带步数 4 入队。(2,3) 处理完转蓝。
19. 21弹出队首 (1,4)(紫,步数 3)。看它上下左右四个方向,能走的空地准备入队。
20. 22把能走的新空地 (1,5)(高亮)标记已访问、带步数 4 入队。(1,4) 处理完转蓝。
21. 23弹出队首 (3,3)(紫,步数 4)。看它上下左右四个方向,能走的空地准备入队。
22. 24把能走的新空地 (3,4)(高亮)标记已访问、带步数 5 入队。(3,3) 处理完转蓝。
23. 25弹出队首 (2,4)(紫,步数 4)。看它上下左右四个方向,能走的空地准备入队。
24. 26把能走的新空地 (2,5)(高亮)标记已访问、带步数 5 入队。(2,4) 处理完转蓝。
25. 27弹出队首 (1,5)(紫,步数 4)。看它上下左右四个方向,能走的空地准备入队。
26. 28(1,5) 四周没有新的可走空地,处理完转蓝。
27. 29弹出队首 (3,4)(紫,步数 5)。看它上下左右四个方向,能走的空地准备入队。
28. 30把能走的新空地 (3,5)(高亮)标记已访问、带步数 6 入队。(3,4) 处理完转蓝。
29. 31弹出队首 (2,5)(紫,步数 5)。看它上下左右四个方向,能走的空地准备入队。
30. 32(2,5) 四周没有新的可走空地,处理完转蓝。
31. 33弹出队首 (3,5)(紫,步数 6)。看它上下左右四个方向,能走的空地准备入队。
32. 34往下的 (4,5) 是边界上的空地,这就是最近出口!当前步数 6 再加这一步 = 7,就是答案。
33. 35沿「从谁来的」回溯,绿色就是入口到最近出口的最短路,一共 7 步。BFS 按步数逐层扩散,所以第一次碰到边界出口时的步数,一定是最近的。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from collections import deque
class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        maze = [list(row) for row in maze]
        m, n = len(maze), len(maze[0])
        sr, sc = entrance
        q = deque([(sr, sc, 0)])
        maze[sr][sc] = '+'
        while q:
            r, c, d = q.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and maze[nr][nc] == '.':
                    if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
                        return d + 1
                    maze[nr][nc] = '+'
                    q.append((nr, nc, d + 1))
        return -1

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        queue<array<int,3>> q;
        q.push({entrance[0], entrance[1], 0});
        maze[entrance[0]][entrance[1]] = '+';
        int dirs[5] = {1,0,-1,0,1};
        while (!q.empty()) {
            auto [r, c, dist] = q.front(); q.pop();
            for (int d = 0; d < 4; ++d) {
                int nr = r + dirs[d], nc = c + dirs[d+1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] == '.') {
                    if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) return dist + 1;
                    maze[nr][nc] = '+';
                    q.push({nr, nc, dist + 1});
                }
            }
        }
        return -1;
    }
};

import java.util.*;
class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{entrance[0], entrance[1], 0});
        maze[entrance[0]][entrance[1]] = '+';
        int[] dirs = {1,0,-1,0,1};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dirs[d], nc = cur[1] + dirs[d + 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && maze[nr][nc] == '.') {
                    if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) return cur[2] + 1;
                    maze[nr][nc] = '+';
                    q.offer(new int[]{nr, nc, cur[2] + 1});
                }
            }
        }
        return -1;
    }
}

复杂度

面试官可能追问