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

In this problem we need to find the shortest path in graph, so the first thing you should think about is bfs or breadth first search. We will keep tuples with 3 elements: (distance, coordinate x, coordinate y). On each step we extract element from the left side of our queue, check if coordinates equal to ending point and if they are, we return distance. If not, for all 8 neighbours, we check if we can visite them: if we still inside grid, if value of grid is equal to 0 and if it was not visited previously. We add new node to visited set and to the end of our queue. (Note, that there is alternative way, where we directly change our grid without using visited set)

Complexity: time complexity is O(N^2): number of nodes in our graph. If we use visited set, space complexity is also O(N^2). If not, it is just O(N), because during traversal there will always be only nodes with distances x and x+1 any given moment and there can be O(N) nodes with every distance.

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

If you like the solution, you can upvote it on leetcode discussion section: Problem 1091