You are given an m x n
matrix maze
(0-indexed) with empty cells (represented as '.'
) and walls (represented as '+'
). You are also given the entrance
of the maze, where entrance = [entrancerow, entrancecol]
denotes the row and column of the cell you are initially standing at.
In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance
. An exit is defined as an empty cell that is at the border of the maze
. The entrance
does not count as an exit.
Return the number of steps in the shortest path from the entrance
to the nearest exit, or -1
if no such path exists.
Example 1:
![](https://assets.leetcode.com/uploads/2021/06/04/nearest1-grid.jpg)
Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] Output: 1 Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3]. Initially, you are at the entrance cell [1,2]. - You can reach [1,0] by moving 2 steps left. - You can reach [0,2] by moving 1 step up. It is impossible to reach [2,3] from the entrance. Thus, the nearest exit is [0,2], which is 1 step away.
Example 2:
![](https://assets.leetcode.com/uploads/2021/06/04/nearesr2-grid.jpg)
Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0] Output: 2 Explanation: There is 1 exit in this maze at [1,2]. [1,0] does not count as an exit since it is the entrance cell. Initially, you are at the entrance cell [1,0]. - You can reach [1,2] by moving 2 steps right. Thus, the nearest exit is [1,2], which is 2 steps away.
Example 3:
![](https://assets.leetcode.com/uploads/2021/06/04/nearest3-grid.jpg)
Input: maze = [[".","+"]], entrance = [0,0] Output: -1 Explanation: There are no exits in this maze.
Constraints:
maze.length == m
maze[i].length == n
1 <= m, n <= 100
maze[i][j]
is either'.'
or'+'
.entrance.length == 2
0 <= entrancerow < m
0 <= entrancecol < n
entrance
will always be an empty cell.
迷宫中离入口最近的出口。
给你一个 m x n 的迷宫矩阵 maze (下标从 0 开始),矩阵中有空格子(用 '.' 表示)和墙(用 '+' 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作,你可以往 上,下,左 或者 右 移动一个格子。你不能进入墙所在的格子,你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ,如果不存在这样的路径,请你返回 -1 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题依然属于比较经典的 flood fill 类型的题。同时既然是找最短路径,那么做法就一定是 BFS。这道题我提供的代码是直接在 input 数组进行修改,当我遇到不是矩阵边缘的空格之后,我把它标记成砖头,这样下次我就不会再重复访问这个坐标了。因为题目给的起点 entrance 不能同时作为出口,所以 steps 的初始化是 1,意思是无论如何肯定是要走的,除非找不到可行解。
时间O(mn)
空间O(1)
Java实现
1 class Solution { 2 public int nearestExit(char[][] maze, int[] entrance) { 3 int m = maze.length; 4 int n = maze[0].length; 5 Queue<int[]> queue = new LinkedList<>(); 6 queue.offer(entrance); 7 maze[entrance[0]][entrance[1]] = '+'; 8 9 int steps = 0; 10 int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 11 while (!queue.isEmpty()) { 12 steps++; 13 int size = queue.size(); 14 for (int i = 0; i < size; i++) { 15 int[] cur = queue.poll(); 16 for (int[] dir : dirs) { 17 int newX = cur[0] + dir[0]; 18 int newY = cur[1] + dir[1]; 19 if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue; 20 if (maze[newX][newY] == '+') continue; 21 22 // return 23 if (newX == 0 || newX == m - 1 || newY == 0 || newY == n - 1) { 24 return steps; 25 } 26 maze[newX][newY] = '+'; 27 queue.offer(new int[] {newX, newY}); 28 } 29 } 30 } 31 return -1; 32 } 33 }
标签:Nearest,Entrance,int,entrance,cell,steps,exit,Exit,maze From: https://www.cnblogs.com/cnoodle/p/16913967.html