1091. Shortest Path in Binary Matrix

https://leetcode.com/problems/shortest-path-in-binary-matrix/

Python

DFS with cache (Timelimit Exceed)

from math import inf
from functools import cache


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] != 0:
            return -1

        n = len(grid)
        visited = set()
        options = [
            (1, 0), (-1, 0), (0, 1),   (0, -1),
            (1, 1), (-1, 1), (-1, -1), (1, -1)
        ]
        min_cost = inf

        @cache
        def dfs(cost, row, col):
            nonlocal min_cost

            if row == n-1 and col == n-1:
                min_cost = min(min_cost, cost)
                return

            if cost > min_cost:
                return

            for rx, cx in options:
                nr, nc = row+rx, col+cx
                if (nr, nc) not in visited \
                   and nr >= 0 and nr < n \
                   and nc >= 0 and nc < n \
                   and grid[nr][nc] == 0:
                    # print((row, col), ">", (nr, nc), visited)
                    visited.add((nr, nc))
                    dfs(cost+1, nr, nc)
                    visited.remove((nr, nc))

        dfs(1, 0, 0)

        return min_cost if min_cost != inf else -1

BFS and remember the distance in place

from collections import deque


class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0] != 0:
            return -1

        n = len(grid)

        directions = [
            (1, 0), (-1, 0), (0, 1),   (0, -1),
            (1, 1), (-1, 1), (-1, -1), (1, -1)
        ]

        queue = deque([(0, 0)])
        grid[0][0] = 1

        while queue:
            row, col = queue.popleft()

            if row == n-1 and col == n-1:
                return grid[row][col]

            for rx, cx in directions:
                nr, nc = row+rx, col+cx
                if nr >= 0 and nr < n \
                   and nc >= 0 and nc < n \
                   and grid[nr][nc] == 0:
                    grid[nr][nc] = grid[row][col] + 1
                    queue.append((nr, nc))

        return -1