Module A-9·11 min read

Grids as implicit graphs — flood fill, multi-source BFS, and the 4/8-directional patterns behind island-counting and rot-spreading problems.

Written by Jatin Jain Saraf · Architect of SupraScan

Module A-9 — Grid Traversal Patterns: Flood Fill and Multi-Source BFS

What this module covers: Modules A-4 and A-5 already used a grid as an implicit graph informally, in passing. This module makes that framing explicit and puts it to work on two named patterns: flood fill (the algorithm behind an image editor's paint bucket tool) and multi-source BFS — starting a single breadth-first search from many points at once, which turns out to be meaningfully different from running several separate single-source searches.

A Grid Is a Graph With Implicit Edges

Every cell in a 2D grid is a node; its up/down/left/right neighbors (4-directional) — or additionally its four diagonal neighbors (8-directional) — are its edges. Nothing about DFS (Module A-4) or BFS (Module A-5) changes when applied to a grid; only how neighbors are generated changes, exactly as Module A-5's shortestPathInGrid already demonstrated.

const directions4 = [[-1, 0], [1, 0], [0, -1], [0, 1]];                     // up, down, left, right
const directions8 = [...directions4, [-1, -1], [-1, 1], [1, -1], [1, 1]];   // + diagonals

Which set to use depends entirely on the problem's own rules — a rook moves 4-directionally, a king moves 8-directionally, and getting this wrong silently changes what counts as "connected."

Flood Fill: Paint Everything Connected

Flood fill starts at one cell and marks every cell reachable from it (through matching, connected cells) — precisely Module A-4's numIslands logic, generalized from "count islands" to "fill this specific region":

function floodFill(grid: number[][], startRow: number, startCol: number, newColor: number): number[][] {
  const rows = grid.length, cols = grid[0].length;
  const originalColor = grid[startRow][startCol];
  if (originalColor === newColor) return grid; // nothing to do — avoids infinite recursion on a no-op fill
 
  function fill(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== originalColor) return; // wrong color, or already repainted to newColor
 
    grid[r][c] = newColor;
    for (const [dr, dc] of directions4) {
      fill(r + dr, c + dc);
    }
  }
 
  fill(startRow, startCol);
  return grid;
}

The if (originalColor === newColor) return grid guard is worth noticing specifically: without it, repainting a cell to the same color it already is would never trigger the grid[r][c] !== originalColor early return, since the color never actually changes — turning what should be a no-op into unbounded recursion. This is exactly the kind of edge case Module A-4's visited set handled explicitly for general graphs; here, the "already painted" check is the visited tracking, folded directly into the color comparison.

Multi-Source BFS: Seed the Queue With Every Source at Once

Rotting Oranges — a grid contains fresh oranges, rotten oranges, and empty cells; every minute, a rotten orange rots every fresh orange adjacent to it; find the minimum time for every fresh orange to rot (or determine it's impossible). The key move: seed the BFS queue with every initially-rotten orange simultaneously, not one at a time.

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const queue: [number, number, number][] = []; // [row, col, minute]
  let freshCount = 0;
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c, 0]); // seed ALL rotten oranges at minute 0, simultaneously
      if (grid[r][c] === 1) freshCount++;
    }
  }
 
  let maxMinute = 0;
  while (queue.length > 0) {
    const [r, c, minute] = queue.shift()!;
    maxMinute = Math.max(maxMinute, minute);
 
    for (const [dr, dc] of directions4) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2; // this fresh orange just rotted
        freshCount--;
        queue.push([nr, nc, minute + 1]);
      }
    }
  }
 
  return freshCount === 0 ? maxMinute : -1; // -1 if some fresh orange was never reached
}