Custom state while iterating over a recursive data structure

Overview

When iterating over a graph over a recursive data structure, we can utilize a custom iteration state. What I mean by this is storing additional helpful information for the given iteration. This would usually be a distance from the current node or similar variables.

Example: Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0. All the adjacent cells of the path are 8-directionally connected (i.e., they are different, and they share an edge or a corner). The length of a clear path is the number of visited cells of this path.

Approach:

In this example, we can notice that we can use BFS to traverse the grid. Our first thought could be to use level order traversal to solve this, but this would be incorrect. Custom state comes very handy in this case. Let's think what we can store... we need to keep track of the distance right? Instead, on each iteration we would store a custom state of (row, col, distance) for each coordinate. This would then give us our shortest path if we reach the coordinates of row == n-1 and col == n-1

Copycopy code to clipboard
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        N = len(grid)
        if grid[0][0] or grid[N-1][N-1]:
            return -1
        # custom state: row, col, distance
        q = deque([(0,0,1)])
        seen = set()
        seen.add((0,0))
        # move in 4 directions + diagonally
        dirs = [[0,1], [1,0], [0,-1], [-1,0], [1,1], [-1,1], [1,-1], [-1,-1]]
        while q:
            r, c, dist = q.popleft()
            if r == c == N-1:
                return dist
            for dx, dy in dirs:
                nr, nc = r + dx, c + dy
                if (
                    0 <= nr < N and 0 <= nc < N and
                    (nr, nc) not in seen and
                    grid[nr][nc] == 0
                ):
                    q.append((nr, nc, dist+1))
                    seen.add((nr, nc))
        return -1