Найдите кратчайший чистый путь от левого верхнего угла до правого нижнего угла матрицы

class Solution:
 
    def shortest_path_binary_matrix(self,
                                    grid: list[list[int, ...]],
                                    __checked: list[tuple, ...] = None,
                                    __row: int = 0,
                                    __col: int = 0,
                                    __calls_num: int = 1) -> int:
 
        n = len(grid) - 1
        if (__row, __col) == (n, n):
            return __calls_num
 
        if __checked is None:
            __checked = [(0, 0)]
 
        possible_ways = [(row, col) for row in range(__row - 1, __row + 2) for col in range(__col - 1, __col + 2)
                         if (row, col) not in __checked and 0 <= row <= n and 0 <= col <= n and 0 == grid[row][col]]
 
        if not possible_ways or grid[0][0] != 0:
            return -1
 
        results = []
        for row, col in possible_ways:
            results.append(self.shortest_path_binary_matrix(grid, __checked + [(row, col)], row, col, __calls_num + 1))
        try:
            return min(tuple(filter(lambda x: x >= 0, results)))
        except ValueError:
            return -1

def test():
    assert Solution().shortest_path_binary_matrix([[0, 1],
                                                   [1, 0]]) == 2
 
    assert Solution().shortest_path_binary_matrix([[0, 0, 0],
                                                   [1, 1, 0],
                                                   [1, 1, 0]]) == 4
 
    assert Solution().shortest_path_binary_matrix([[1, 0, 0],
                                                   [1, 1, 0],
                                                   [1, 1, 0]]) == -1
 
    assert Solution().shortest_path_binary_matrix([[1, 0, 0],
                                                   [0, 0, 0],
                                                   [0, 0, 0]]) == -1
 
    assert Solution().shortest_path_binary_matrix([[0, 0, 0],
                                                   [0, 0, 0],
                                                   [0, 0, 0]]) == 3
 
    # FIXME: этот тест выполняется очень долго
    assert Solution().shortest_path_binary_matrix([[0, 0, 1, 1, 0, 0],
                                                   [0, 0, 0, 0, 1, 1],
                                                   [1, 0, 1, 1, 0, 0],
                                                   [0, 0, 1, 1, 0, 0],
                                                   [0, 0, 0, 0, 0, 0],
                                                   [0, 0, 1, 0, 0, 0]]) == 8
 
 
if __name__ == '__main__':
    test()

import heapq
 
 
class Solution:
    def shortest_path_binary_matrix(self, grid):
        n = len(grid)
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return -1
        
        # Создаем список смежности графа
        graph = [[] for _ in range(n*n)]
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    node = i*n+j
                    # Добавляем ребра для соседних ячеек
                    if i > 0 and grid[i-1][j] == 0:
                        graph[node].append((node-n, 1))
                    if j > 0 and grid[i][j-1] == 0:
                        graph[node].append((node-1, 1))
                    if i < n-1 and grid[i+1][j] == 0:
                        graph[node].append((node+n, 1))
                    if j < n-1 and grid[i][j+1] == 0:
                        graph[node].append((node+1, 1))
        
        # Запускаем алгоритм Дейкстры
        heap = [(0, 0)]  # Куча вершин для обработки
        dist = [float('inf')] * (n*n)  # Расстояние от начальной вершины до остальных
        dist[0] = 0
        
        while heap:
            d, node = heapq.heappop(heap)
            if node == n*n-1:
                return d
            if d > dist[node]:
                continue
            for neighbor, weight in graph[node]:
                new_dist = d + weight
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    heapq.heappush(heap, (new_dist, neighbor))
        
        return -1

from collections import deque
 
def BFS(matr):
    visited = set()
    inserted = {}
    n = len(matr)
    Ai, Aj = 0, 0
    Bi, Bj = n-1, n-1
    dec = deque()
    if matr[Ai][Aj] != 0:
        return -1
    dec.append((Ai, Aj))
    inserted[(Ai,Aj)] = 1
    while dec:
        i, j = dec.popleft()
        cur_dist = inserted[(i, j)]
        visited.add((i, j))
        if (i, j) == (Bi, Bj):
            return cur_dist
        for next_i, next_j in ((i+1,j+1), (i+1,j), (i,j+1), (i+1,j-1), (i-1,j+1), (i,j-1), (i-1,j), (i-1,j-1)):
            if not (next_i in range(n) and next_j in range(n)):
                continue
            if matr[next_i][next_j] == 0 and not (next_i, next_j) in visited:
                if not (next_i, next_j) in inserted:
                    inserted[(next_i, next_j)] = cur_dist + 1
                    dec.append((next_i, next_j))
    return -1
 
print(BFS([ [0, 0, 1, 1, 0, 0],
            [0, 0, 0, 0, 1, 1],
            [1, 0, 1, 1, 0, 0],
            [0, 0, 1, 1, 0, 0],
            [0, 0, 0, 0, 0, 0],
            [0, 0, 1, 0, 0, 0]]))

class Solution:
    def shortestPathBinaryMatrix(self, grid)->int:
        n=len(grid)
        if grid[0][0]==0 and grid[n-1][n-1]==0:
            if n==1:
                return 1
            dx = [ -1, 0, 1, 1, 1, 0, -1, -1 ]
            dy = [ -1, -1, -1, 0, 1, 1, 1, 0 ]
            from collections import deque
            d=deque()
            d.append((0,0,1))
            while len(d)>0:
                s=d.popleft()
                for i in range(8):
                    x=s[0]+dx[i]
                    if x>=0 and x<n:
                        y=s[1]+dy[i]
                        ns=s[2]+1
                        if y>=0 and y<n and grid[y][x]==0:
                            if x==n-1 and y==n-1:
                                return ns
                            else:
                                grid[y][x]=1;
                                d.append((x,y,ns))
        return -1