--- title: 'Grid Traversal' source: 'https://academia.sh/en/courses/advanced-algorithms/grid-traversal' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:29+00:00' license: 'CC BY-SA 4.0' --- # Grid Traversal Connected-component search on a matrix; how the connectivity definition changes the answer on 38 grids, and what marking and traversal choice do to held cell count. All seven patterns in this topic so far worked on one-dimensional data: an array, a stream, a successor chain. The last pattern handles data in **two dimensions**. A grid has filled cells, and the question is: how many sets of cells connected to one another are there. A grid is not really a new structure. Every filled cell is a node, every pair of neighboring cells is an edge; what is asked is the number of **connected components**, and the procedure was established in the Data Structures course. Breadth-first and depth-first search themselves, why marking a visit is required, and the $O(V + E)$ cost were measured there; they are **not repeated** here, they are used directly. What the pattern adds is the modeling, and that is where its precondition sits: **what connectivity means.** This lesson counts how many different answers two connectivity definitions produce on the same grid. ## Problem, Oracle, and Pattern The oracle does no traversal at all. It scans every pair of filled cells, groups adjacent ones together, and repeats until no merge remains. The pattern starts a breadth-first search from every unvisited filled cell, and every search counts as one component. **PP56.** The corpus is 40 grids; each grid is 8×8, and every cell is filled with a probability of 30 in 100. Seed `20260218`. **PP57.** Two connectivity definitions are measured: **4-connectivity** (edge-adjacent cells only) and **8-connectivity** (corner-adjacent cells included too). **PP58.** The oracle and the pattern are run **separately** with each connectivity definition; all four combinations are measured. This shows whether a divergence comes from the pattern or from a difference in definition. **PP59.** The visit is marked **on enqueue**; this is the rule established in the Breadth-First Search lesson and its rationale is not repeated here. ```python from collections import deque SEED, SIZE, CORPUS_SIZE = 20260218, 8, 40 def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def grid_corpus(seed=SEED, n=CORPUS_SIZE, size=SIZE): r = generator(seed) return [{"no": i + 1, "grid": [[1 if r(101) < 30 else 0 for _ in range(size)] for _ in range(size)]} for i in range(n)] class Counter: def __init__(self): self.step = 0 def count(self): self.step += 1 def adjacent(a, b, connectivity): di, dj = abs(a[0] - b[0]), abs(a[1] - b[1]) return di + dj == 1 if connectivity == 4 else max(di, dj) == 1 and (di or dj) def oracle_component(grid, connectivity, s): """Scans every cell pair, groups adjacent ones, repeats until no change. Always correct, always expensive.""" cell = [(i, j) for i, row in enumerate(grid) for j, v in enumerate(row) if v] group = {h: i for i, h in enumerate(cell)} changed = True while changed: changed = False for a in range(len(cell)): for b in range(a + 1, len(cell)): s.count() if adjacent(cell[a], cell[b], connectivity) and \ group[cell[a]] != group[cell[b]]: old, new = group[cell[b]], group[cell[a]] for h in cell: if group[h] == old: group[h] = new changed = True return len(set(group.values())) DIR4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) DIR8 = DIR4 + ((-1, -1), (-1, 1), (1, -1), (1, 1)) def pattern_bfs(grid, connectivity, s): """The Data Structures course's breadth-first search is used directly: the visit is marked ON ENQUEUE.""" direction = DIR4 if connectivity == 4 else DIR8 n, m = len(grid), len(grid[0]) visited, component, widest = set(), 0, 0 for i in range(n): for j in range(m): if not grid[i][j] or (i, j) in visited: continue component += 1 visited.add((i, j)) queue = deque([(i, j)]) while queue: widest = max(widest, len(queue)) x, y = queue.popleft() s.count() for dx, dy in direction: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and grid[a][b] \ and (a, b) not in visited: visited.add((a, b)) queue.append((a, b)) return component, widest K = grid_corpus() filled = sum(sum(sum(row) for row in k["grid"]) for k in K) print("corpus:", len(K), "grids x", SIZE, "x", SIZE, "| filled cells:", filled, "| average", round(filled / len(K), 2)) print("pattern connectivity oracle connectivity diverging/40 pattern oracle ratio") for pc in (4, 8): for oc in (4, 8): diverging, pk, ok = 0, 0, 0 for record in K: s1, s2 = Counter(), Counter() a, _ = pattern_bfs(record["grid"], pc, s1) b = oracle_component(record["grid"], oc, s2) pk, ok = pk + s1.step, ok + s2.step diverging += (a != b) print(f"{pc:19d} {oc:19d} {diverging:10d} {pk:5d} {ok:6d}" f" {ok / pk:6.1f}") ``` ``` corpus: 40 grids x 8 x 8 | filled cells: 723 | average 18.07 pattern connectivity oracle connectivity diverging/40 pattern oracle ratio 4 4 0 723 12768 17.7 4 8 38 723 12834 17.8 8 4 38 723 12768 17.7 8 8 0 723 12834 17.8 ``` The diagonal rows are zero, the other two are **38**. When the pattern uses the **same connectivity definition** as the oracle, it gives the same answer on 40 of 40 grids; once the definitions diverge, 38 of 40 grids diverge. This table makes one thing certain: **the divergence does not come from the pattern.** Breadth-first search works correctly with either definition; what is broken is not the pattern itself, it is the **connectivity definition** given to it. The pattern's step count is **723** in both definitions, the oracle's is 12,768 to 12,834; the ratio is **17.7**. The step column is nearly identical across all four rows and gives no signal at all about the diverging-input column. ## Connectivity Is Not a Data Property, It Is a Decision In the previous seven patterns, the precondition was a property of the input: sorted or not, negative or not, duplicate or not. Here the precondition is not in the input; it is **a decision made by whoever modeled the problem**, and cannot be verified by looking at the data. The small grid below shows this in a glance. **PP60.** The small example is built by hand; it comes from no generator and exists only to show the divergence between the two definitions. **PP61.** The second corpus comes from seed `20260219`. What is measured is **how many grids** the two definitions give a different component count on. ```python from collections import deque def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def grid_corpus(seed, n=40, size=8): r = generator(seed) return [[[1 if r(101) < 30 else 0 for _ in range(size)] for _ in range(size)] for _ in range(n)] DIR4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) DIR8 = DIR4 + ((-1, -1), (-1, 1), (1, -1), (1, 1)) def component(grid, connectivity): """Component count by breadth-first search; the visit is marked on enqueue.""" direction = DIR4 if connectivity == 4 else DIR8 n, m = len(grid), len(grid[0]) visited, count = set(), 0 for i in range(n): for j in range(m): if not grid[i][j] or (i, j) in visited: continue count += 1 visited.add((i, j)) queue = deque([(i, j)]) while queue: x, y = queue.popleft() for dx, dy in direction: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and grid[a][b] \ and (a, b) not in visited: visited.add((a, b)) queue.append((a, b)) return count small = [[1, 0, 0, 0, 1], [0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [1, 0, 0, 0, 1]] for row in small: print(" ", "".join("#" if v else "." for v in row)) print(" 4-connectivity:", component(small, 4), "components") print(" 8-connectivity:", component(small, 8), "components") print() print("seed 4-connectivity total 8-connectivity total differing grid/40") for seed in (20260218, 20260219): K = grid_corpus(seed) d4 = [component(g, 4) for g in K] d8 = [component(g, 8) for g in K] differing = sum(1 for a, b in zip(d4, d8) if a != b) print(f"{seed} {sum(d4):17d} {sum(d8):17d} {differing:16d}") ``` ``` #...# .#.#. ..#.. .#.#. #...# 4-connectivity: 9 components 8-connectivity: 1 components seed 4-connectivity total 8-connectivity total differing grid/40 20260218 387 233 38 20260219 377 227 38 ``` The five-row grid has nine cells and none of them is edge-adjacent; all of them sit on a diagonal. With 4-connectivity there are **9 separate components**; with 8-connectivity, **a single component**. Same data, same procedure, a ninefold difference. In the forty-grid corpus, total component count drops from **387 to 233**, and the two definitions give a different answer on **38 grids**. In the second corpus the numbers are 377 and 227, differing grids again **38**; the result does not depend on the corpus. The practical conclusion of this measurement is this: **the first question to ask when reading a grid problem is what connectivity means.** If the definition is not written in the problem statement, the correctness of the pattern's answer cannot be tested — not even the oracle can be built, because the oracle needs the same definition too. This is the topic's only precondition that **cannot be determined by looking at the data**. ## Marking and Traversal Change What Is Held, Not the Answer Once connectivity is fixed, two implementation decisions remain: whether marking happens on enqueue or on dequeue, and whether the traversal is breadth-first or depth-first. Neither changes the component count. What they change is the **number of cells held at once**. **PP62.** This measurement is done on a larger grid: 10 grids, each 20×20, cells filled with probability 60 in 100. In a small, sparse grid the difference between these three procedures falls below the resolution. **PP63.** What is measured is, for breadth-first search, the **queue's widest point**, and for depth-first search, the **largest value of recursion depth**. ```python from collections import deque def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def grid_corpus(seed=20260218, n=10, size=20): r = generator(seed) return [[[1 if r(101) < 60 else 0 for _ in range(size)] for _ in range(size)] for _ in range(n)] DIR4 = ((-1, 0), (1, 0), (0, -1), (0, 1)) def bfs(grid, on_enqueue): """Is marking done ON ENQUEUE or ON DEQUEUE.""" n, m = len(grid), len(grid[0]) visited, component, step, widest = set(), 0, 0, 0 for i in range(n): for j in range(m): if not grid[i][j] or (i, j) in visited: continue component += 1 queue = deque([(i, j)]) if on_enqueue: visited.add((i, j)) while queue: widest = max(widest, len(queue)) x, y = queue.popleft() step += 1 if not on_enqueue: if (x, y) in visited: continue visited.add((x, y)) for dx, dy in DIR4: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and grid[a][b] \ and (a, b) not in visited: if on_enqueue: visited.add((a, b)) queue.append((a, b)) return component, step, widest def dfs(grid): """Recursive depth-first search; the deepest stack size is measured.""" n, m = len(grid), len(grid[0]) visited, component, step, deepest = set(), 0, 0, 0 def visit(x, y, depth): nonlocal step, deepest step += 1 deepest = max(deepest, depth) visited.add((x, y)) for dx, dy in DIR4: a, b = x + dx, y + dy if 0 <= a < n and 0 <= b < m and grid[a][b] \ and (a, b) not in visited: visit(a, b, depth + 1) for i in range(n): for j in range(m): if grid[i][j] and (i, j) not in visited: component += 1 visit(i, j, 1) return component, step, deepest K = grid_corpus() base = [bfs(g, True) for g in K] print("corpus: 10 grids x 20 x 20 | filled cells:", sum(sum(sum(row) for row in g) for g in K)) print("traversal same component steps most held cells") for ad, result in (("bfs, mark on enqueue ", base), ("bfs, mark on dequeue ", [bfs(g, False) for g in K]), ("dfs (recursive) ", [dfs(g) for g in K])): same = sum(1 for a, b in zip(result, base) if a[0] == b[0]) print(f"{ad} {same:12d} {sum(x[1] for x in result):4d}" f" {max(x[2] for x in result):20d}") ``` ``` corpus: 10 grids x 20 x 20 | filled cells: 2378 traversal same component steps most held cells bfs, mark on enqueue 10 2378 18 bfs, mark on dequeue 10 2887 24 dfs (recursive) 10 2378 103 ``` All three rows give the same component count: 10 of 10 grids match. Diverging inputs are **zero**, and these rows are not a correctness measurement. The difference measured sits in two columns instead. Marking on dequeue raises steps from 2378 to **2887** and the widest queue from 18 to **24**: the same cell enters the queue more than once before being visited. Depth-first search's step count is **identical** to breadth- first search's (2378), but its deepest stack holds **103** cells — roughly **five and a half times** breadth-first search's widest queue. This last number is a practical limit. On a dense, large grid, recursive depth-first search demands a stack depth proportional to the grid's size; breadth-first search demands a queue proportional to the widest layer. Which is cheaper depends on the grid's **shape**, and this distinction was already established in the Data Structures course's comparison table; here the same distinction is confirmed numerically. ## Three Numbers | Metric | Oracle | Pattern | Diverging input | |---|---|---|---| | 4-connectivity, 4-connectivity | 12,768 steps | 723 steps | **0/40** | | 8-connectivity, 4-connectivity | 12,768 steps | 723 steps | **38/40** | | Breadth-first search, 20×20 grid | — | 2378 steps / 18 cells | **0/10** | | Depth-first search, 20×20 grid | — | 2378 steps / 103 cells | **0/10** | In the first two rows the pattern's step count is **identical**, and diverging inputs range from 0 to 38; in the last two rows diverging inputs are identical and held cell count changes by five and a half times. Two kinds of decision show up in two separate columns — and neither leaves a trace in the other's column. ## Summary - A grid is a graph: filled cells are nodes, adjacent cell pairs are edges; connected- component counting is done with the Data Structures course's breadth-first and depth-first search. - When the pattern uses the same connectivity definition as the oracle, it is correct on 40 of 40 grids; once the definitions diverge, it diverges on **38 grids**, and the pattern's step count is 723 in both cases. - Connectivity is a decision made by whoever models the problem, not a property of the data; it cannot be determined by looking at the data, and the oracle cannot even be built without it. - A nine-cell diagonal grid gives 9 components under 4-connectivity and 1 under 8-connectivity; the total over the 40-grid corpus drops from 387 to 233. - Marking on dequeue does not change the answer but raises steps from 2378 to 2887 and the queue from 18 to 24; depth-first search holds a stack of 103 cells at the same step count. ## Next Step This topic measured eight patterns under the same frame: an oracle, a pattern, and the number of inputs where the two diverge. In all eight lessons, the source of divergence was not a bug in the pattern — it was **an accepted but unchecked precondition**: order, sign, single successor, sort key, value range, balance, the question's definition, and connectivity. The next topic moves from patterns to **named problems**: the knapsack, the traveling salesman, the longest path, the n-queens placement. The question asked there changes — not whether a pattern's precondition has broken, but why a problem is **hard**; and the oracle remains the tool by which that hardness is measured.