---
# System prepended metadata

title: '**Leetcode筆記(Nearest Exit from Entrance in Maze)**'
tags: [graph, medium, leetcode]

---

# **Leetcode筆記(Nearest Exit from Entrance in Maze)**


:::info
:information_source: 題目 : Nearest Exit from Entrance in Maze, 類型 : graph , 等級 : medium
日期 : 2024/08/25
:::


### 嘗試
```python

```

---
### **優化**
好久都沒有寫leetcode了，為了回歸fulltime做準備，加油啦!!
這題解法非常經典，但還是邊看解答邊寫，加油!!
```python
class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m, n = len(maze), len(maze[0])
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        s_r, s_c = entrance[0], entrance[1]

        visited = set()
        visited.add((s_r, s_c))
        
        q = deque()
        q.append((s_r, s_c, 1))

        while q:
            r, c, step = q.popleft()

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc

                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and maze[nr][nc] == ".":
                    # check exit
                    if nr == 0 or nr == m - 1 or nc == 0 or nc == n - 1:
                        return step
                    else:
                        visited.add((nr, nc))
                        q.append((nr, nc, step + 1))

        return -1
```
---



**思路**


**講解連結**

Provided by. 
