• n == grid.length == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1
• The start or the end cell may itself be blocked.

Two words in this statement decide everything: shortest and path. Together they say we are looking for a minimum number of steps through a network of positions where each step costs exactly the same. That last part — every step costs 1 — is the property that makes this easy, and recognising it is the transferable skill.

The obvious approach is to walk out of the start cell, try each of the 8 directions, and from each of those try 8 more, remembering the best complete route found. Written recursively that is a depth-first exploration of every possible walk.

The cost is catastrophic. Each cell branches up to 8 ways, and a walk can be as long as the number of cells, so the count of distinct walks grows like 8 raised to the power of n². Even for a 5×5 grid that is an astronomically large number. Worse, it does not naturally terminate — a walk can step back and forth between two cells forever unless you track the current path and undo the marks when you back out.

But the real waste is more specific than "too many walks". Suppose the search reaches cell (3,4) after 6 steps, explores everything beyond it, then later reaches (3,4) again after 9 steps. The second visit re-explores the identical territory to produce results that cannot possibly beat the first. Everything reachable from a cell depends only on the cell, not on how you arrived. So arriving at a cell a second time, by a longer route, is pure repetition — and a search that reaches every cell once instead of once per route would be finite and fast.

Here is a different way to organise the search. Instead of following one route to its conclusion, expand outward from the start in rings of equal distance.

The set of cells at distance 1 is exactly the clear neighbours of the start. The set at distance 2 is exactly the unvisited clear neighbours of those. And so on. Each ring is computed entirely from the previous ring, and — this is the crucial part — a cell first appears in the ring matching its true shortest distance. It cannot appear earlier, because reaching it would require a shorter route that by definition does not exist; and it will not appear later, because the moment any distance-d cell is expanded, every neighbour of it is claimed for ring d+1.

So the first time the destination shows up, you already have the answer, and you can stop. No comparing of alternative routes, no bookkeeping of a best-so-far. The order of discovery is the ordering by distance.

This ring-by-ring expansion is called Breadth-First Search. The name describes the shape: it goes wide before it goes deep.

To expand rings you need to hold the current frontier somewhere and process it in the order cells were discovered. That is a queue — a list you add to at the back and remove from the front, first in, first out. The FIFO discipline is not an implementation detail; it is what keeps the rings from mixing. If you removed from the back instead, you would have a stack, the search would plunge down one route before finishing the current ring, and distances would no longer come out in order. Same code, completely different algorithm.

Alongside the queue you carry each cell's distance, and a record of which cells have already been claimed.

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
        return -1

    queue = deque([(0, 0, 1)])      # row, col, cells visited so far
    grid[0][0] = 1                  # claim the start immediately

    while queue:
        r, c, dist = queue.popleft()
        if r == n - 1 and c == n - 1:
            return dist

        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1            # claim on discovery, not on removal
                    queue.append((nr, nc, dist + 1))
    return -1

The nested loop over dr and dc generates all 9 offsets including (0,0), but that one is harmless: the current cell is already marked, so it fails the == 0 test and is skipped.

Every cell is claimed once and inspected once, and each inspection looks at 8 neighbours, so the work is proportional to the number of cells: O(n²) time, with O(n²) memory for the queue in the worst case.

Marking cells as they are claimed, and tracking the queue as a list of (cell, distance):

Note that the target was found on the pop, not the push. Checking on the push would also be correct here and slightly faster, but checking on the pop keeps the loop uniform and is easier to reason about.

Now consider [[1,0,0],[1,1,0],[1,1,0]]. The guard fires before any search begins, since grid[0][0] is 1, and the answer is -1. Without that guard, the code would claim a blocked start and walk out of it, reporting a path that does not exist.

The precondition BFS depends on is narrow and worth stating precisely: every edge must cost the same. The ring argument works because a cell at distance d has all its neighbours at distance d+1 — no cheaper and no dearer. The instant steps have different costs, that collapses: a two-step route could be cheaper than a one-step route, so first-discovered would no longer mean nearest, and you would need Dijkstra's algorithm, which replaces the queue with a priority queue ordered by accumulated cost.

Signals that BFS is the intended tool in an unseen statement: the words shortest, minimum number of steps, fewest moves, earliest time — combined with moves that are all interchangeable. If instead the question asks whether something is reachable at all, or how many separate regions exist, or asks you to enumerate every configuration, distance is irrelevant and depth-first search is simpler and lighter on memory.

Memory is the real trade. DFS holds one route, so O(depth). BFS holds an entire ring, which on a wide grid can be thousands of cells at once. You pay that memory for the guarantee that the first arrival is the best arrival.

One upgrade worth knowing for this specific problem, since the destination is fixed and known: A\ search. Plain BFS expands rings in every direction equally, including away from the target. A\ keeps the frontier in a priority queue ordered by steps-taken plus an optimistic estimate of steps-remaining — here, the Chebyshev distance to the corner, which is the number of diagonal-inclusive moves needed if nothing were blocking. Because that estimate never overstates the true remaining cost, the answer stays optimal, but the search leans toward the goal and touches far fewer cells.

Train the reflex: whenever a problem asks for a minimum number of identical steps, stop looking for a clever formula and ask what a node is and what an edge is. If every edge costs the same, BFS answers it, and the first time you touch the goal you are done.