Flood fill and regions
A flood fill starts at one cell and spreads to every connected cell. Keep a stack of cells to visit and a set of cells already reached:
seen = {(r, c)}
todo = [(r, c)]
while todo:
r, c = todo.pop()
for each neighbour (nr, nc) that is in bounds,
of the right kind, and not in seen:
seen.add((nr, nc))
todo.append((nr, nc))Mark a cell as seen when you push it, so it is never pushed twice. Use a loop like this instead of recursion: a winding region of a few thousand cells goes deeper than Python's recursion limit.
To count regions, scan the grid; each time you meet a cell not yet seen, add one to the count and flood from it. Decide up front what connects cells (4 or 8 directions) and what a region is made of (one colour, or any open cell).
Watch the visual: the set grows one reachable cell at a time.
See it run
plan = [[".", "#"], [".", "."]] seen = {(0, 0)} todo = [(0, 0)] while todo: r, c = todo.pop() for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]: if 0 <= nr < 2 and 0 <= nc < 2 and plan[nr][nc] == "." and (nr, nc) not in seen: seen.add((nr, nc)) todo.append((nr, nc)) print(len(seen))
Start at the top-left cell. Water reaches every open cell it can walk to.
Practice flood fill and regions
Exercise 1
A floor plan is a list of equal-length strings: "." is open floor and "#" is wall. Water starts at row row, column col and spreads from a wet cell to the open cells directly above, below, left and right of it, again and again.
Return how many cells end up wet.
Rules:
- Water never enters a wall and never leaves the plan.
- Only the 4 direct neighbours count; the start cell itself is wet.
- If the start cell is a wall, nothing is wet: return 0.
- Open cells that the water cannot reach stay dry.
Constraints: plan up to 60×60 (3600 cells). A long winding corridor is possible, so very deep recursion may fail: use a stack or queue.
Example: solution(["..#.", "..#.", "###."], 0, 0) returns 4: the 2×2 room on the left is sealed off by walls.
Exercise 2
A quilt is a list of equal-length strings; each character is a fabric colour. A patch is a group of cells with the same character where you can get from any cell of the group to any other by steps up, down, left or right, staying on that character, and that cannot be extended by a neighbouring cell of the same character.
Return the number of patches in the quilt.
Rules:
- Only the 4 direct neighbours connect cells. Cells that touch only diagonally belong to different patches.
- The same colour can form several separate patches.
- Colours are case-sensitive.
Constraints: 1 ≤ rows, columns ≤ 60.
Example: solution(["AAB", "ABB", "AAB"]) returns 2: one connected patch of A and one of B. solution(["AB", "BA"]) returns 4, since the matching cells only touch diagonally.
Exercise 3
A quilt is a list of equal-length strings; each character is a fabric colour. A patch is a maximal group of cells with the same character that are connected by steps up, down, left or right (staying on that character).
Return the number of cells in the largest patch.
Rules:
- Only the 4 direct neighbours connect cells; diagonal contact does not.
- A patch that is a single cell has size 1.
- Colours are case-sensitive.
Constraints: 1 ≤ rows, columns ≤ 100. The grid can be one huge patch, so look up visited cells in a set, not a list.
Example: solution(["AAB", "ABB", "AAB"]) returns 5 (the five connected A cells; the B patch has four). solution(["AB", "BA"]) returns 1.
The explanation and tasks are public. Running this lesson requires an account with course access.
Practice
Loading Python…Visualizer Watch your code run line by line
Run your code, then choose Play to follow its execution.