엔지니어 게시판
LeetCode 솔루션 분류

# [11/21] 1926. Nearest Exit from Entrance in Maze

• 학부유학생 작성
• 작성일

• 81 조회
• 1 댓글
• 0 추천
• 0 비추천

### 본문

Medium
152857Add to ListShare

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 updownleft, 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:

```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:

```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:

```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.
Accepted
63,725
Submissions
129,260
태그

댓글 1

## 학부유학생님의 댓글

• 작성일
Runtime: 1120 ms, faster than 77.13% of Python3 online submissions for Nearest Exit from Entrance in Maze.
Memory Usage: 15.6 MB, less than 27.25% of Python3 online submissions for Nearest Exit from Entrance in Maze.
``````from collections import deque
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
ROW, COL = len(maze), len(maze[0])

visited = set()
visited.add((entrance[0],entrance[1]))

queue = deque([(entrance[0], entrance[1], 0)])

directions = [(1,0), (0,1), (-1,0),(0,-1)]

while queue:
r, c, steps = queue.popleft()

if (r == 0 or r == ROW - 1 or c == 0 or c == COL -1) and (r,c) != (entrance[0],entrance[1]):
return steps

for rdir, cdir in directions:
nr, nc = r+rdir, c+cdir
if 0<=nr<ROW and 0<=nc<COL and (nr, nc) not in visited and maze[nr][nc] == ".":
queue.append((nr, nc, steps+1))
visited.add((nr, nc))

return -1``````
전체 307 / 1 페이지

• 등록일 04:05
• 등록일 04:04
• 등록일 04:04
• 등록일 04:04
• 등록일 04:03
• 등록일 04:02
• 등록일 04:01
• 등록일 04:00
• 등록일 04:00
• 등록일 00:27

• 등록일 11.29
• 등록일 11.29
• 등록일 11.26

### Stats

• 현재 접속자 29 명
• 오늘 방문자 755 명
• 어제 방문자 2,154 명
• 최대 방문자 2,154 명
• 전체 회원수 451 명