Grid as GraphGrids as graphs

01Why it exists

Reach for it when you see:Two-dimensional grids, m × n, four-way adjacency, how many regions or islands, the largest one, flood fill, fewest steps through a maze, distance to the nearest something, working inward from the border.

02The core idea

A grid is already a graph: every cell (r, c) is a node, and two cells that sit next to each other vertically or horizontally, both of them walkable, have an undirected edge between them. Those edges never need to be stored. A direction array DIRS = [(-1,0), (1,0), (0,-1), (0,1)] plus the current coordinates produces the neighbours on the spot, so BFS and DFS carry over untouched; the only change is that "list the neighbours of u" becomes four bounds checks instead of an adjacency-list lookup. An m × n grid has V = mn nodes, and the edge count peaks when every cell is walkable: E = m(n−1) + n(m−1) < 2mn.

Grid problems almost always come in one of two shapes. Counting connected regions: a double loop scans every cell, and on an unvisited walkable cell you do count += 1 and traverse its whole region, marking as you go. That count is exactly the number of components, because one traversal marks every cell of the component the start belongs to (a connected cell always gets pushed) and marks only that component (a disconnected cell has no edge leading to it), so when the scan later reaches another unmarked cell it must belong to a component nobody has counted yet. Fewest steps: every move costs 1, so BFS applies, and the dist recorded the first time a cell is marked is the shortest number of steps. When there are many starting points, push them all at distance 0 at the same time — this is multi-source BFS, and it gives each cell its distance to the closest of them. The question "which cells cannot reach the border?" is the same idea in reverse: treat every walkable border cell as a start, traverse once, and the cells never reached are the answer.

Complexity: each cell is marked at most once and enters and leaves the queue once, checking 4 directions each time, which is O(4mn) = O(mn) — just O(V + E) with the grid's numbers substituted in. The outer scan has to look at every cell anyway, so counting regions has no better best case. Space is O(mn) for the visited or dist array, and in the worst case the queue or stack can hold O(mn) cells at once. Written recursively, DFS has a recursion depth equal to the length of the current path, and one snaking strip of land is enough to push that to mn levels: a 1000×1000 grid means a million frames, Python's default recursion limit is only 1000, and C++'s default stack will not survive it either. On large grids, use BFS or an explicit stack.

The usual mistakes: check the bounds before you read, because Python's grid[-1] does not raise — it reads the last row, so an out-of-range -1 quietly wraps around to the far side; mark on push, because marking only when you pop lets several neighbours queue the same cell; and four directions versus eight depends on the problem, so DIRS needs 8 entries when a diagonal move also counts as one step. Overwriting visited land with 0 saves you the visited array but destroys the input. Unlike the grid backtracking in Word Search, a mark here is never undone; visiting each cell exactly once is what makes it O(mn). When cells cost different amounts to enter, switch to Dijkstra; when cells turn into land one at a time and you have to report the island count as you go, switch to a union-find.

03The algorithm

1. 1Define the graph: m = len(grid), n = len(grid[0]), decide which cells are walkable (land, not wall), and write down DIRS (four directions, or eight). Do not build a separate adjacency list.
2. 2Set up the marking: an m × n boolean array seen, or a dist array when you need step counts, with -1 for not reached yet.
3. 3Traverse one region: mark the start and push it. Pop (r, c), compute (nr, nc) for each (dr, dc), and check in order that 0 ≤ nr < m, that 0 ≤ nc < n, that the cell is walkable, and that it is not marked yet. Only when all four pass do you mark it and push it.
4. 4Count regions: scan every cell with a double loop, and on an unmarked walkable cell add one to the region count and run step 3 from it, accumulating the area as you pop if you need it.
5. 5Fewest steps: with a single start, run BFS directly with dist[nr][nc] = dist[r][c] + 1; with several starts (the nearest exit, every ocean cell, every border cell), push them all at distance 0 first and then run the same loop.

04Interactive demo

A 5×6 map where 1 is land and 0 is water, holding 5 islands in all. The demo scans cell by cell and, on a piece of land it has not visited, traverses that whole island: yellow cells are waiting in the queue or on the stack, blue is the cell being processed, a green outline marks the walkable neighbours found on this step, and a cell that has been popped and processed is replaced by the number of the island it belongs to. Switch between "BFS (queue)" and "DFS (stack)" — the only difference in the code is whether you take from the front or the back. Cells inside one island finish in a different order, but the island count and the membership of each island come out exactly the same.

05Code

Two functions for the two kinds of question: island_areas uses BFS to measure each island's area (on the very map from the demo), and nearest_exit uses multi-source BFS for every cell's distance to the closest exit, including one cell that is walled in and reaches no exit at all. Both share the same skeleton — direction array, bounds check, mark on push — and once that is second nature, most grid problems come down to deciding which cells are walkable and where the traversal starts.

from collections import deque

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]    # up, down, left, right


def island_areas(grid):
    """1s joined in four directions form an island. Returns each area in scan order; the length is the island count."""
    m, n = len(grid), len(grid[0])
    seen = [[False] * n for _ in range(m)]
    areas = []
    for r in range(m):
        for c in range(n):
            if grid[r][c] != 1 or seen[r][c]:
                continue
            seen[r][c] = True                 # unvisited land: the start of a new island
            queue, area = deque([(r, c)]), 0
            while queue:
                cr, cc = queue.popleft()      # queue.pop() makes it the stack version; same areas
                area += 1
                for dr, dc in DIRS:
                    nr, nc = cr + dr, cc + dc
                    # Check bounds first: Python's grid[-1] does not raise, it quietly reads the last row
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1 and not seen[nr][nc]:
                        seen[nr][nc] = True   # mark on push, so no cell is ever queued twice
                        queue.append((nr, nc))
            areas.append(area)
    return areas


def nearest_exit(floor):
    """Multi-source BFS: steps from each cell to the nearest exit E. Walls # and unreachable cells are -1."""
    m, n = len(floor), len(floor[0])
    dist = [[-1] * n for _ in range(m)]
    queue = deque()
    for r in range(m):
        for c in range(n):
            if floor[r][c] == "E":
                dist[r][c] = 0                # every exit starts in the queue at distance 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and floor[nr][nc] != "#" and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1  # the first time a cell is reached is the fewest steps
                queue.append((nr, nc))
    return dist


if __name__ == "__main__":
    grid = [
        [1, 1, 0, 0, 0, 1],
        [1, 0, 0, 1, 0, 1],
        [0, 0, 1, 1, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 1],
    ]
    areas = island_areas(grid)
    print(len(areas), areas, max(areas))   # 5 [3, 2, 4, 1, 1] 4

    floor = ["E.#...",
             "..#.#.",
             "....#E",
             "##.##.",
             "#.#..."]
    for r, row in enumerate(nearest_exit(floor)):
        print(" ".join(" #" if floor[r][c] == "#" else f"{d:2}" for c, d in enumerate(row)))
    # Output (# is a wall; (4, 1) is fenced in by walls and reaches no exit, hence -1):
    #  0  1  #  4  3  2
    #  1  2  #  5  #  1
    #  2  3  4  5  #  0
    #  #  #  5  #  #  1
    #  # -1  #  4  3  2

06Practice

• LeetCode 733Flood Fill (the most basic four-direction traversal)Easy
• LeetCode 1020Number of Enclaves (traverse inward from the border)Medium
• LeetCode 54201 Matrix (multi-source BFS)Medium
• LeetCode 417Pacific Atlantic Water Flow (one traversal from each coast)Medium
• LeetCode 934Shortest Bridge (mark one island, then multi-source BFS)Medium
• LeetCode 827Making A Large Island (label islands with areas, then try every 0)Hard