# 1926. Nearest Exit from Entrance in Maze
###### tags: `leetcode` `1926` `medium` `bfs`

## :memo: Question

## :memo: 題意
* 給你一個護士的位置，他要找出最近的出口要走幾步，有障礙物的不能走，出口的定義是超出 matrix 的邊界，但如果護士一開始就在最邊界，那個邊界就不算出口，走不到出口就回傳-1。

## :memo: my solution
* :medal: **思考一**: 看到走迷宮，bfs 不用考慮。
* :medal: **思考二**: 要紀錄已經走過的路，不然會走回頭路。

## :memo: my solution code

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
    
        m = len(maze)
        n = len(maze[0])
        visitedmatrix = [[0 for i in range(n)] for i in range(m)]
        queue = deque([entrance+[0]])
        visitedmatrix[entrance[0]][entrance[1]] = 1
        
        while queue:
        
            x, y, d = queue.popleft()
            
            for newx, newy in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]]:
                if 0 <= newx < m and 0 <= newy < n and not visitedmatrix[newx][newy] and maze[newx][newy] == ".":
                    visitedmatrix[newx][newy] = 1
                    queue.append([newx,newy, d+1])
                    
                elif (newx < 0 or newy < 0 or newx == m or newy == n) and d != 0:
                    return d
                
        return -1 

## :memo: BigO
* 時間複雜度: O(m+n)。
* 空間複雜度: O(m+n)。