Problem statement

https://binarysearch.com/problems/Escape-Maze/

Solution

Variation of Leetcode 1091. Shortest Path in Binary Matrix.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, grid):
        N, M = len(grid), len(grid[0])
        neibs = [[-1,0],[0,-1],[0,1],[1,0]]
        queue = deque([(1, 0, 0)]) if grid[0][0] == 0 else deque()
        V = set()
        
        while queue:
            dist, x, y = queue.popleft()
            if (x, y) == (N-1, M-1): return dist
            for dx, dy in neibs:
                if 0<=x+dx<N and 0<=y+dy<M and grid[x+dx][y+dy] == 0 and (x+dx, y+dy) not in V:
                    V.add((x+dx,y+dy))
                    queue.append((dist + 1, x+dx, y+dy))
                
        return -1