1091. Shortest Path in Binary Matrix

We do as the problem says — you can either use a DFS or a BFS. I did a DFS.

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [
            (0, 1),
            (1, 0),
            (1, 1),
            (-1, -1),
            (-1, 1),
            (1, -1),
            (0, -1),
            (-1, 0),
        ]
        visited = set()
        start = deque([((0, 0), 1)])
 
        def inbounds(x, y):
            return 0 <= x < m and 0 <= y < n
 
        while start:
            (x, y), dist = start.popleft()
            if not inbounds(x, y):
                continue
            if (x, y) in visited or grid[x][y] == 1:
                continue
            visited.add((x, y))
            if x == m - 1 and y == n - 1:
                return dist
            for dx, dy in dirs:
                start.append(((dx + x, dy + y), dist + 1))
        
        return -1