# 2.23 Flood Fill

Flood fill explores a connected region in a grid starting from a seed cell and marks or transforms all cells that belong to the same region. Connectivity is defined by a neighborhood relation, typically 4-directional or 8-directional.

## Problem

Given a grid `a`, a starting cell `(sr, sc)`, and a new value `newVal`, replace all cells connected to `(sr, sc)` that have the same original value with `newVal`.

Example:

```text id="q2y9sn"
1 1 1
1 1 0
1 0 1
```

Starting at `(0, 0)` with `newVal = 2`:

```text id="b7h3mt"
2 2 2
2 2 0
2 0 1
```

## Connectivity

Four-directional neighbors:

```text id="k8d1wr"
up, down, left, right
```

Eight-directional adds diagonals. Choose one model and use it consistently.

## Depth-First Search (DFS)

Recursive DFS is the most direct implementation.

```go id="c4x8vt"
func FloodFillDFS(a [][]int, sr, sc, newVal int) {
	rows := len(a)
	if rows == 0 {
		return
	}
	cols := len(a[0])

	old := a[sr][sc]
	if old == newVal {
		return
	}

	var dfs func(int, int)
	dfs = func(r, c int) {
		if r < 0 || r >= rows || c < 0 || c >= cols {
			return
		}
		if a[r][c] != old {
			return
		}

		a[r][c] = newVal

		dfs(r-1, c)
		dfs(r+1, c)
		dfs(r, c-1)
		dfs(r, c+1)
	}

	dfs(sr, sc)
}
```

## Invariant

```text id="v1z4qx"
Every cell visited by dfs has the original value old and is connected to the seed
Every such cell is eventually recolored to newVal
```

Marking the cell before recursive calls prevents revisiting.

## Breadth-First Search (BFS)

BFS uses a queue and avoids recursion depth limits.

```go id="r6t3kp"
func FloodFillBFS(a [][]int, sr, sc, newVal int) {
	rows := len(a)
	if rows == 0 {
		return
	}
	cols := len(a[0])

	old := a[sr][sc]
	if old == newVal {
		return
	}

	type cell struct{ r, c int }
	q := []cell{{sr, sc}}

	a[sr][sc] = newVal

	for len(q) > 0 {
		cur := q[0]
		q = q[1:]

		dirs := [][2]int{
			{-1, 0}, {1, 0}, {0, -1}, {0, 1},
		}

		for _, d := range dirs {
			nr := cur.r + d[0]
			nc := cur.c + d[1]

			if 0 <= nr && nr < rows && 0 <= nc && nc < cols && a[nr][nc] == old {
				a[nr][nc] = newVal
				q = append(q, cell{nr, nc})
			}
		}
	}
}
```

## Invariant

```text id="j9y2sn"
All cells in the queue belong to the region and will be processed exactly once
Cells already recolored will not be enqueued again
```

## Visited Tracking

Flood fill often uses the grid itself to mark visited cells by changing their value. If the grid must remain unchanged, use a separate visited matrix.

```go id="y4p8gx"
visited := make([][]bool, rows)
for i := range visited {
	visited[i] = make([]bool, cols)
}
```

Then check and mark `visited[r][c]` instead of modifying `a`.

## Eight-Directional Fill

Replace direction list:

```go id="k1w6mz"
dirs := [][2]int{
	{-1, -1}, {-1, 0}, {-1, 1},
	{0, -1},           {0, 1},
	{1, -1},  {1, 0},  {1, 1},
}
```

Connectivity becomes more permissive.

## Counting Region Size

Instead of recoloring, count the number of cells in the region.

```go id="p3c7rv"
func RegionSize(a [][]int, sr, sc int) int {
	rows := len(a)
	if rows == 0 {
		return 0
	}
	cols := len(a[0])

	target := a[sr][sc]
	count := 0

	var dfs func(int, int)
	dfs = func(r, c int) {
		if r < 0 || r >= rows || c < 0 || c >= cols {
			return
		}
		if a[r][c] != target {
			return
		}

		a[r][c] = -1 // mark visited
		count++

		dfs(r-1, c)
		dfs(r+1, c)
		dfs(r, c-1)
		dfs(r, c+1)
	}

	dfs(sr, sc)
	return count
}
```

## Boundary Flood Fill

Flood fill can be applied from all boundary cells to mark reachable regions, for example in problems involving enclosed areas.

Pattern:

```text id="h2d5pq"
Start DFS or BFS from boundary cells
Mark reachable cells
Process remaining unmarked cells
```

## Complexity

Let `n = rows * cols`.

```text id="r7f2xm"
Time:  O(n)
Space: O(n) worst case for recursion stack or queue
```

Each cell is visited at most once.

## Common Pitfalls

Not checking `old == newVal` causes infinite recursion or unnecessary work.

Forgetting boundary checks leads to out-of-range errors.

Not marking visited cells before recursive calls causes repeated visits.

Using recursion on large grids can overflow the call stack. Use BFS or an explicit stack in such cases.

Mixing 4-directional and 8-directional logic leads to inconsistent results.

## Design Pattern

Flood fill follows:

1. Identify the target value
2. Start from a seed
3. Expand to neighbors that match the target
4. Mark visited cells immediately
5. Continue until no new cells are reachable

## Takeaway

Flood fill is a graph traversal on a grid where edges connect neighboring cells. Use DFS for simplicity and BFS for stack safety. Correctness depends on consistent neighbor definition, proper boundary checks, and immediate marking of visited cells.