Grid Traversal as Graph BFS/DFS

Grid traversal treats each cell as a node with 4- or 8-neighbor edges—BFS/DFS for shortest steps or connected regions.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Map (r,c) to index r*m+c if needed. Mark visited in grid or dist matrix. Walls block edges.

Try this in Python

from collections import deque


def bfs_shortest(adj: list[list[int]], start: int) -> list[int]:
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist


print(bfs_shortest([[1, 2], [0], [0]], 0))

Common mistakes

• Out of bounds neighbors.
• Revisiting cells without visited (TLE).

Key takeaways

• Multi-source BFS from all gates at once.
• 0-1 BFS on grid with move costs 0/1.