DSA Patterns Made Simple · Trees and Graphs
Graphs and Grids: Flood Fill with DFS and BFS
A grid is a graph where each cell's neighbours are up, down, left and right. Count islands with a flood fill, and find shortest paths with BFS, remembering which cells you've already visited.
The problem
Number of Islands: in a map of 1 (land) and 0 (water), how many separate islands are there? Land cells connect up, down, left and right.
How to spot it
- A 2D grid of cells: islands, rooms, mazes, rotting oranges, flood fill
- "Connected", "groups", "regions", "can I reach…"
- Shortest path / fewest steps in an unweighted grid or graph → BFS
- An explicit graph: a list of edges or an adjacency list
The idea
Think of pouring paint on one land cell: it spreads to every connected land cell. Each time you find unpainted land, that's a new island; paint it all, then keep scanning.
- DFS flood fill (recursion or a stack) for "which cells are connected?".
- BFS (queue) when you need the fewest steps, because it explores cells in order of distance.
- Always keep a visited record (or mark the grid itself) so you never process a cell twice. Without it, you loop forever.
Neighbours of (r, c) are (r+1, c), (r-1, c), (r, c+1), (r, c-1), if they're inside the grid.
The template
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def neighbours(r, c):
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
yield nr, nc
# BFS for fewest steps
queue = deque([(start, 0)])
seen = {start}
while queue:
cell, dist = queue.popleft()
if cell == goal:
return dist
for nxt in neighbours(*cell):
if nxt not in seen and is_open(nxt):
seen.add(nxt) # mark when you enqueue
queue.append((nxt, dist + 1))
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
// BFS for fewest steps
let frontier = [start], dist = 0;
const seen = new Set([key(start)]);
while (frontier.length) {
const next = [];
for (const [r, c] of frontier) {
if (r === goal[0] && c === goal[1]) return dist;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (inside(nr, nc) && isOpen(nr, nc) && !seen.has(key([nr, nc]))) {
seen.add(key([nr, nc])); // mark when you enqueue
next.push([nr, nc]);
}
}
}
frontier = next;
dist++;
}
Worked example
Count islands with an iterative DFS (a stack avoids recursion limits on big grids), then find the fewest steps through a maze with BFS.
from collections import deque
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
seen = set()
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
islands += 1 # new island: paint all of it
stack = [(r, c)]
seen.add((r, c))
while stack:
cr, cc = stack.pop()
for dr, dc in DIRS:
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and (nr, nc) not in seen:
seen.add((nr, nc))
stack.append((nr, nc))
return islands
def shortest_path(maze, start, goal):
rows, cols = len(maze), len(maze[0])
queue = deque([(start, 0)])
seen = {start}
while queue:
(r, c), dist = queue.popleft()
if (r, c) == goal:
return dist
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == "." and (nr, nc) not in seen:
seen.add((nr, nc))
queue.append(((nr, nc), dist + 1))
return -1
grid = ["11000",
"11000",
"00100",
"00011"]
print("islands:", count_islands(grid))
maze = ["..#....",
".##.##.",
"...#...",
"#.....#"]
print("fewest steps:", shortest_path(maze, (0, 0), (0, 6)))
print("unreachable:", shortest_path([".#.", "##.", "..."], (0, 0), (2, 2)))
Output
islands: 3 fewest steps: 12 unreachable: -1
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function countIslands(grid) {
const rows = grid.length, cols = grid[0].length;
const seen = new Set();
let islands = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] !== "1" || seen.has(`${r},${c}`)) continue;
islands++; // new island: paint all of it
const stack = [[r, c]];
seen.add(`${r},${c}`);
while (stack.length) {
const [cr, cc] = stack.pop();
for (const [dr, dc] of DIRS) {
const nr = cr + dr, nc = cc + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === "1" && !seen.has(`${nr},${nc}`)) {
seen.add(`${nr},${nc}`);
stack.push([nr, nc]);
}
}
}
}
}
return islands;
}
function shortestPath(maze, start, goal) {
const rows = maze.length, cols = maze[0].length;
let frontier = [start], dist = 0;
const seen = new Set([`${start[0]},${start[1]}`]);
while (frontier.length) {
const next = [];
for (const [r, c] of frontier) {
if (r === goal[0] && c === goal[1]) return dist;
for (const [dr, dc] of DIRS) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && maze[nr][nc] === "." && !seen.has(`${nr},${nc}`)) {
seen.add(`${nr},${nc}`);
next.push([nr, nc]);
}
}
}
frontier = next;
dist++;
}
return -1;
}
const grid = ["11000",
"11000",
"00100",
"00011"];
console.log("islands:", countIslands(grid));
const maze = ["..#....",
".##.##.",
"...#...",
"#.....#"];
console.log("fewest steps:", shortestPath(maze, [0, 0], [0, 6]));
console.log("unreachable:", shortestPath([".#.", "##.", "..."], [0, 0], [2, 2]));
Output
islands: 3 fewest steps: 12 unreachable: -1
Common mistakes
- Marking visited when you pop instead of when you push. The same cell gets queued many times; mark it as soon as you add it.
- Recursive DFS on big grids. A 1000×1000 all-land grid means a million nested calls; use an explicit stack.
- Going out of bounds. Check
0 <= r < rowsand0 <= c < colsbefore reading a cell. - Using DFS for "fewest steps". DFS finds a path, not the shortest; BFS finds the shortest in unweighted graphs.
Practice
- Number of Islands (medium)
Key points
- Grid = graph with up/down/left/right neighbours.
- Count regions: scan cells, flood-fill each new one (DFS with a stack).
- Fewest steps in an unweighted grid: BFS.
- Mark visited when enqueuing. O(rows × cols) time.
Practice questions
Why does BFS find the shortest path in an unweighted grid, but DFS doesn't?
Answer
BFS explores cells in increasing order of distance from the start (all cells 1 step away, then 2, …), so the first time it reaches the goal is via a shortest path. DFS follows one path as deep as it can and may reach the goal by a long route first.
Why mark a cell as visited when it is added to the queue rather than when it is removed?
Answer
Otherwise several neighbours can add the same cell before it's processed, so it's queued (and processed) multiple times, which wastes time and can blow up memory.
Open in the app to mark lessons complete, take notes and track your progress.