DFS (Flood Fill)

In one sentence

Depth-first search keeps walking forward to an unvisited neighbour, and only steps back when it is stuck. Flood fill is DFS on a grid: start in one cell and "pour paint" until the whole region is coloured.

1. What problem does it solve?

Example — 723D · Lakes in Berland (rating 1600)

A map is an \(n \times m\) grid of water . and land *, surrounded by ocean. A lake is a maximal region of water cells connected by sides that does not touch the border of the map (water touching the border flows into the ocean).

Turn the fewest water cells into land so that exactly \(k\) lakes remain. Print that number and the new map.

Limits: \(n, m \le 50\), \(0 \le k \le 50\). The map has at least \(k\) lakes.

Input        Output
5 4 1
****         1
*..*         ****
****         *..*
**.*         ****
..**         ****
             ..**

The sample has two lakes and one ocean region:

****        ****
*..*        *AA*     A: lake of 2 cells
****   ->   ****
**.*        **B*     B: lake of 1 cell
..**        OO**     O: touches the border, so it is ocean, not a lake

We must keep \(1\) lake, so we fill one of them. Filling B costs \(1\) cell and filling A costs \(2\), so we fill B.

The idea:

1. Find every water region with flood fill, and note its cells and whether it touches the border.
2. Keep only the real lakes and sort them by size.
3. Fill the smallest (number of lakes − k) lakes.

Step 3 is greedy, and it is clearly optimal: we must remove exactly that many lakes, and filling a lake costs its size, so pick the smallest ones.

2. How DFS works

2.1 The grid is a graph

Each cell is a vertex. Two water cells that share a side are joined by an edge. A water region is a connected component (see Graph Concepts). The neighbours of \((x, y)\) are:

            (x-1, y)
(x, y-1)    (x,   y)    (x, y+1)
            (x+1, y)

In code, the four moves are stored as two lists, dx and dy. Changing the movement rule (8 directions, knight moves…) means changing only these lists.

2.2 The recursive walk

dfs(x, y) does three things:

1. Mark \((x, y)\) as visited.
2. For each of the four neighbours, check bounds and skip cells outside the grid.
3. If the neighbour is water and not visited, call dfs on it.

Here is DFS started at the top-left water cell of a bigger lake. The template tries neighbours in the order right, left, down, up, and the numbers show the order cells are visited:

*******
*123***     1 → 2 → 3          go right as far as possible
***4***     3 → 4 → 5          no right, no left: go down
***56**     5 → 6              right
*******     6 is stuck: every call returns, back to 1

The recursion goes deep first and only returns when a cell has no unvisited neighbours. That is where the name comes from.

2.3 Why it paints exactly one region

• It only moves between adjacent water cells, so everything painted is in the region.
• If some cell \(t\) of the region stayed unpainted, walk the path from the start to \(t\) and look at the first unpainted cell on it. Its predecessor was painted, so dfs checked this cell as a neighbour and would have painted it. Contradiction.
• visited stops any cell from being painted twice.

Cost: each cell is visited once and checks 4 neighbours, so a full scan is \(O(nm)\). For Lakes in Berland that is \(2500\) cells.

2.4 The call stack, and why Python can crash

Every call that has not returned yet waits on the call stack. A snake-shaped lake in a \(50 \times 50\) map can have about \(1250\) cells in one line of calls. Python's default limit is \(1000\), so dfs would crash with RecursionError.

fix	how
raise the limit	uncomment the skeleton's sys.setrecursionlimit(...). Fine for grids up to a few tens of thousands of cells.
explicit stack	replace recursion with a list used as a stack: append to push, pop to take the newest cell. Needed for grids like \(1000 \times 1000\).

Lakes in Berland is small, so the worked solution keeps the recursive template and raises the limit.

3. Template

This is the DFS template from our slides (USACO Algorithm — From Bronze to Silver, 16 Jan). N, M and grid come from the problem.

# Setup
visited = set()
dx = [0, 0, 1, -1] # Directions
dy = [1, -1, 0, 0]

def dfs(x, y):
    visited.add((x, y))

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # Check Bounds
        if nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue

        # Check if empty and not visited
        if (nx, ny) not in visited and grid[nx][ny] == '.':
            dfs(nx, ny)

4. Worked solution — Lakes in Berland

The template, plus two additions: dfs also records the cells it paints in cells, and we check whether any of them lies on the border.

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10000)


def solve():
    N, M, k = map(int, input().split())
    grid = [list(input().strip()) for _ in range(N)]

    visited = set()
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    cells = []

    def dfs(x, y):
        visited.add((x, y))
        cells.append((x, y))

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue

            if (nx, ny) not in visited and grid[nx][ny] == '.':
                dfs(nx, ny)

    lakes = []
    for i in range(N):
        for j in range(M):
            if grid[i][j] != '.' or (i, j) in visited:
                continue
            cells = []
            dfs(i, j)
            ocean = False
            for x, y in cells:
                if x == 0 or x == N - 1 or y == 0 or y == M - 1:
                    ocean = True
            if not ocean:
                lakes.append(cells)

    lakes.sort(key=lambda lake: len(lake))

    filled = 0
    for lake in lakes[:len(lakes) - k]:
        for x, y in lake:
            grid[x][y] = '*'
        filled += len(lake)

    print(filled)
    for row in grid:
        print("".join(row))


solve()

Why cells = [] works inside dfs

dfs only calls cells.append(...), which changes the list object but never assigns to the name cells. Python then looks up cells in solve, where the loop rebinds it to a fresh list before each fill.

\"\".join(row) here

Each row is one line of output, and join just turns the list of characters back into that line. It is not batching many answers into one print.

5. DFS beyond grids

The same shape works on any graph stored as an adjacency list. The only change is "for each neighbour":

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

On a tree, you can also compute things on the way back from the recursion. For example, subtree size: size[u] = 1 + sum(size[child]). That is how 1676G · White-Black Balanced Subtrees is solved.

6. Common mistakes

grid[x][y] with x and y mixed up

x is the row and must satisfy 0 <= x < N. y is the column and must satisfy 0 <= y < M. On a non-square grid, mixing them up gives IndexError or silently wrong answers.

Checking bounds after indexing

grid[nx][ny] with nx = -1 does not crash in Python. It reads the last row. Always check bounds first, as the template does.

Grid rows as strings when you need to change them

Strings cannot be modified. Read rows with list(input().strip()) if you will write grid[x][y] = '*'.

Forgetting the ocean

Water that touches the border is not a lake. Filling it wastes cells and changes the lake count wrongly.

RecursionError

See §2.4. Raise the limit for small grids; use an explicit stack for big ones.

7. Practice

Problem	Set	Rating	Idea
723D · Lakes in Berland	—	1600	this page
1829F · Forever Winter	5-Graph · A	1300	graph reasoning, a DFS warm-up
1676G · White-Black Balanced Subtrees	5-Graph · B	1300	DFS on a tree, compute on return
1800E1 · Unforgivable Curse (easy)	5-Graph · K	1400	components of positions, compare letter counts
1800E2 · Unforgivable Curse (hard)	5-Graph · E	1500	same, with positions that cannot move
1702E · Split Into Two Sets	5-Graph · D	1600	DFS through components, check cycle lengths

---

Credits & licenses

• Section structure follows USACO Guide — Flood Fill by Darren Yao, licensed CC BY-NC-SA 4.0.
• The template in §3 is from our slides. Everything else (the lake analysis, traces, worked solution, mistakes) is ours.