Leetcode 2038 Solution

This article provides solution to leetcode question 2038 (nearest-exit-from-entrance-in-maze)
Categories:
Tags:
Access this page by simply typing in "lcs 2038" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/nearest-exit-from-entrance-in-maze

Solution

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        m = len(maze)
        n = len(maze[0])



        q = collections.deque()
        visited = set()



        q.append((entrance[0], entrance[1]))
        visited.add((entrance[0], entrance[1]))



        step = 0
        while q:
            s = len(q)



            for _ in range(s):
                i, j = q.popleft()



                for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    ni, nj = i + di, j + dj



                    if not (0 <= ni < m and 0 <= nj < n):
                        if (i, j) != (entrance[0], entrance[1]):
                            return step
                        else:
                            continue



                    if maze[ni][nj] == '+':
                        continue



                    if (ni, nj) in visited:
                        continue



                    q.append((ni, nj))
                    visited.add((ni, nj))
            step += 1



        return -1