LeetCode 1926. 迷宫中离入口最近的出口（BFS）

Michael阿明

发布于 2021-09-06 11:18:23

2970

发布于 2021-09-06 11:18:23

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

给你一个 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 一定是空格子。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/nearest-exit-from-entrance-in-maze 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

标准的广度优先搜索模板题

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size(), step = 0;
        typedef pair<int,int> pii;
        queue<pii> q;
        q.push({entrance[0], entrance[1]});
        maze[entrance[0]][entrance[1]] = '+'; // 访问过了
        vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
        while(!q.empty())
        {
            int size = q.size();
            step++;
            while(size--)
            {   
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for(int k = 0; k < 4; ++k)
                {
                    int nx = x + dir[k][0];
                    int ny = y + dir[k][1];
                    if(nx>=0 && nx<m && ny>=0 && ny<n && maze[nx][ny]!='+') //不为墙
                    {
                        if(nx==0 || nx==m-1 || ny==0 || ny==n-1)
                            return step; // 到达边界出口
                        maze[nx][ny] = '+'; // 标记为走过了
                        q.push({nx, ny});
                    }
                }
            }
        }
        return -1;
    }
};

100 ms 29.1 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

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

原始发表：2021/07/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https