【BFS最短路问题】迷宫中离入口最近的出口

利刃大大

发布于 2025-03-03 08:10:36

5700

代码可运行

文章被收录于专栏：csdn文章搬运

运行总次数：0

代码可运行

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

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

每一步操作，你可以往上，下，左或者右移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的 空格子。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 一定是空格子。

解题思路：广度优先遍历

其实这类最短路径问题，和前面的 floodfill 算法问题是差不多的，大体代码框架还是那样子！

这道题无非就是给定一个起点，然后 找出从起点到边界的权值总和最小的路径，而每一步的权值是 1。所以我们可以用一个变量 step 记录下路径长度，从起点做一个广度优先遍历，将其临近的并且符合要求的节点添加到队列中，此时判断一下如果这些节点中如果就是边界节点的话，则直接返回 step，如果不是的话则继续做广度优先遍历。

如果最后都没找到边界节点的话，说明没有出口，则直接返回 -1。

然后在 bfs 途中和 floodfill 算法不同的是，我们要将每一层队列中的节点拎出来做 bfs，也就是每一层队列有 size 个，则对这层做 size 次 bfs，而不是不停的做 bfs，因为我们要控制一层一层往外走，就得控制每次操作的是一层的节点，就像二叉树的层序遍历一样。

class Solution {
private:
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();

        // 将起点加入到队列中
        queue<pair<int, int>> bfs;
        bfs.push({entrance[0], entrance[1]});
        maze[entrance[0]][entrance[1]] = '+';

        int step = 0;
        while(!bfs.empty())
        {
            step++; // 每一层广度就让step++

            int size = bfs.size();
            while(size--)
            {
                auto [x, y] = bfs.front();
                bfs.pop();

                for(int i = 0; i < 4; ++i)
                {
                    int newx = x + dx[i], newy = y + dy[i];
                    if(newx >= 0 && newy >= 0 && newx < m && newy < n && maze[newx][newy] == '.')
                    {
                        // 如果遇到了出口，此时就是最短路径了，直接返回step即可
                        if(newx == 0 || newx == m - 1 || newy == 0 || newy == n - 1)
                            return step;

                        bfs.push({newx, newy});
                        maze[newx][newy] = '+';
                    }
                }
            }
        }
        return -1; // 如果没找到出口的话，则返回-1
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-03-02，如有侵权请联系 cloudcommunity@tencent.com 删除

队列