Grids as implicit graphs
A grid can be searched as a graph, with each open cell as a vertex and an edge between two open cells that share a side. Many problems are set on a grid like that, such as a map of land and water or a maze. The first one here counts the islands on a map:
You get a grid of "1" (land) and "0" (water) cells. An island is a group of land cells joined through shared sides; two cells that touch only at a corner are not joined. Water surrounds the whole grid. Return the number of islands.
Constraints
- The grid has rows and columns,
- Each cell is
"0"or"1"
Sample 1 ยท Input
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
Output
1
Sample 2 ยท Input
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output
3
The second sample is this grid, with its rows numbered down the side and its columns along the bottom:
We name a cell by its row and then its column, so the land cell in the middle of the grid is (2, 2). The four land cells in the top-left corner touch along their sides, so they form one island. The cell (2, 2) touches that block only at a corner, and corners do not join cells, so it is an island by itself. The cells (3, 3) and (3, 4) are the third island, and the answer is 3.
In this grid the vertices are the land cells, and two land cells that share a side are joined by an edge. An island is a connected component of that graph, so counting islands is counting components, which takes a new search from every vertex that no earlier search has reached.
We never build this graph as adjacency lists. A search asks an adjacency list for one thing, the neighbors of the vertex it is at, and the neighbors of a cell can be worked out from its row and column. So the search reads the grid directly, as if the grid were the adjacency list. A graph like this, whose edges follow from a rule and are never written down, is called an implicit graph.
Neighbors from offsets
Take the cell (1, 2) of any grid. The cells beside it are (2, 2) below it, (1, 3) to its right, (0, 2) above it and (1, 1) to its left. We call these four its neighbors, whatever they hold. Each is (1, 2) with 1 added to or subtracted from the row or the column. We write these four changes as pairs, , , and , where the first number is added to the row and the second to the column. Such a pair is called an offset, and the same four offsets give the neighbors of any cell (r, c).
(r, c) to its four side neighbors, with the diagonal offsets drawn faintly. Right: at the corner (0, 0), two of the four offsets leave the grid.For a cell on the edge of the grid, some of the results are not cells. At the corner (0, 0), in the right half of the figure, the offsets and lead to row and to column . So after adding an offset (dr, dc), we keep the new position (nr, nc) only when nr is between 0 and rows - 1 and nc is between 0 and cols - 1. This program prints the neighbors of the corner in a grid of 4 rows and 5 columns:
DIRECTIONS = [(1, 0), (0, 1), (-1, 0), (0, -1)] # down, right, up, left
rows, cols = 4, 5
r, c = 0, 0
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
print(nr, nc)It prints 1 0 and 0 1, the cells below and to the right of the corner. Every search in this lesson contains this loop, with one more test in the if for what the problem allows, such as that the neighbor is land.
In Python, leaving out the two 0 <= tests raises no error, because is a valid index: grid[-1] is the last row of the grid. The search then steps from the top row to the bottom row. In a grid of one column with the rows "1", "0" and "1", it joins the two land cells and counts one island where there are two.
Some problems also allow diagonal moves. A cell then has up to eight neighbors, and the list of offsets gets four more entries, , , and . The loop stays the same. On Number of Islands the extra offsets would be a mistake: they join all seven land cells of our grid into one island.
Flood fill
Now we can mark a whole island. We start at one land cell, and the search moves from each cell it reaches to that cell's land neighbors until it finds no new one. A search used this way, to mark everything joined to a starting cell, is called a flood fill. The paint-bucket tool of a drawing program is one: it recolors the pixel you click and every pixel joined to it through pixels of the same color.
The fill is a depth-first search that keeps its waiting cells on a stack, with cells in place of vertices:
- Mark the starting cell and push it on a stack.
- Pop a cell. Look at its four neighbors, and for each one that is inside the grid, is land and is not marked, mark it and push it.
- Repeat step 2 until the stack is empty.
Let's follow these steps from (0, 0) on the grid of the first part. The neighbors are tried in the order of our offsets: down, right, up, left.
| Cell popped | Marked and pushed | Stack afterwards |
|---|---|---|
| none yet | (0, 0) | (0, 0) |
| (0, 0) | (1, 0), (0, 1) | (1, 0), (0, 1) |
| (0, 1) | (1, 1) | (1, 0), (1, 1) |
| (1, 1) | none | (1, 0) |
| (1, 0) | none | empty |
When (1, 1) is popped, its neighbors (2, 1) and (1, 2) are water, and (0, 1) and (1, 0) are land that is already marked, so nothing is pushed. Without the marks, the fill would go around the block of four cells forever.
The row for (1, 1) also shows why a cell is marked when it is pushed and not when it is popped. At that moment (1, 0) is still waiting on the stack, and without a mark it would be pushed a second time and popped twice. Marking at the push keeps each cell on the stack at most once.
When the stack is empty, four cells are marked:
These four cells are the whole island, and a fill always marks exactly the island of its starting cell. It never leaves the island, because each push follows one move from a land cell to a land cell beside it.
It misses no part of the island either. Take any cell of the island and a path of land cells that leads to it from the start. The start is marked. Each marked cell on the path was pushed when it got its mark, so it is popped before the fill ends, and when it is popped the next cell on the path gets its mark, unless it already has one. Cell by cell, the marks reach the end of the path.
With a different test in step 2, the same fill marks a room of open floor in a maze or a patch of one color in a picture. What a fill from one cell marks is called a region: a group of cells joined to each other by allowed moves, with no allowed move leading out of the group. A region is a connected component of the grid's graph.
Counting regions
One fill marks one island. To count the islands, we scan the grid row by row, and each time the scan reaches a land cell that is not marked, we add 1 to the count and fill from that cell. The fill marks the rest of that island, so the scan passes over those cells when it reaches them.
On our grid the scan starts three fills:
The cell (3, 4) is land as well, but the third fill marks it before the scan gets there, so the count ends at 3.
Step through the scan
The widget runs the scan on the same grid, and its first steps are the rows of the table in Flood fill. The number in a cell is the order in which it was popped, and a dashed outline marks a cell that is waiting on the stack. Switching from Depth-first to Breadth-first replaces the stack with a queue: the numbers change, and the islands stay the same.
The fill and the scan in code
In the program, flood_fill is the three steps of Flood fill, started at the cell (sr, sc), and count_islands is the scan. The marks are kept in seen, a grid of true and false values of the same size as the input.
DIRECTIONS = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def flood_fill(grid, seen, sr, sc):
rows, cols = len(grid), len(grid[0])
seen[sr][sc] = True
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and not seen[nr][nc]:
seen[nr][nc] = True
stack.append((nr, nc))
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and not seen[r][c]:
islands += 1
flood_fill(grid, seen, r, c)
return islands
print(count_islands(["11110", "11010", "11000", "00000"]))
print(count_islands(["11000", "11000", "00100", "00011"]))Prints 1 and 3, the answers to the two samples.
Each cell is pushed at most once, because it is marked at that moment and a marked cell is never pushed again. Popping a cell looks at four neighbors, so the fills together make at most four neighbor checks per cell. For the largest grid the problem allows:
That is far below the rough budget of steps a second. The grid's graph has at most vertices and at most four edges at each one, so the of a graph search is here, and the seen grid and the stack take memory of the same order.
A solution can do without the seen grid by changing each "1" that the fill reaches to "0". Water is never filled, so the change works as a mark whenever the caller does not need the grid back. It needs rows that are lists, as LeetCode passes them; the strings in our two calls cannot be changed.
Deeper read: the recursive fill
The fill can also be written as a recursive function. The function returns at once for a position that is outside the grid, is water or is already marked. Otherwise it marks the cell and calls itself on the four neighbors. count_islands calls it as before.
def flood_fill(grid, seen, r, c):
if not (0 <= r < len(grid) and 0 <= c < len(grid[0])):
return # outside the grid
if grid[r][c] != "1" or seen[r][c]:
return # water, or already marked
seen[r][c] = True
flood_fill(grid, seen, r + 1, c)
flood_fill(grid, seen, r, c + 1)
flood_fill(grid, seen, r - 1, c)
flood_fill(grid, seen, r, c - 1)This version marks the same cells, and the call stack does the work of our stack. Its limit is depth, because the calls nest along the route the fill takes. On an island that winds back and forth, the route passes through every cell before the first call returns:
In a 300 by 300 grid, an island of this form has 150 full rows and 150 single cells, which is cells, and the calls nest that deep.
Python stops at about 1,000 nested calls, so on that island the recursive fill ends in a RecursionError. The version with its own stack returns 1.
Searching from the border
Each fill so far started from one cell. A fill can also start from several: we mark and push all of them before the loop begins, and the loop then marks every cell joined to any of them. The next problem is solved by one such fill.
You get a board of "X" and "O" cells. "O" cells joined through shared sides form a region, and a region is surrounded when none of its cells lies on the edge of the board. Change every "O" in a surrounded region to "X", in place, and leave every other cell alone.
Constraints
- The board has rows and columns,
- Each cell is
"X"or"O"
Sample 1 ยท Input
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Sample 2 ยท Input
board = [["X"]]
Output
[["X"]]
The first sample and its answer, side by side:
The three "O" cells in the middle form a region that touches no edge, so all three become "X". The fourth "O", at (3, 1), lies on the bottom edge. Its region is that single cell, and it stays.
The cells that stay are easier to find than the cells that change. An "O" stays when its region contains an edge cell, and then a fill started from that edge cell reaches it. So one fill started from every "O" on the edge marks all the cells that stay:
- Go over the edge of the board. Change each
"O"there to"S", for safe, and push it. - Run the fill: pop a cell, and change each
"O"among its neighbors to"S"and push it. - Go over the whole board. Each
"O"that is left is surrounded and becomes"X". Each"S"goes back to"O".
The letter "S" is the mark. The problem asks us to change the board in place, so the board itself can hold the marks. In the first sample, step 1 finds one "O" on the edge, at (3, 1). All of its neighbors are "X", so the fill in step 2 ends at once, and step 3 changes the three "O" cells that are left.
DIRECTIONS = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def capture_surrounded(board):
rows, cols = len(board), len(board[0])
stack = []
for r in range(rows): # step 1: every O on the edge
for c in range(cols):
on_edge = r == 0 or r == rows - 1 or c == 0 or c == cols - 1
if on_edge and board[r][c] == "O":
board[r][c] = "S"
stack.append((r, c))
while stack: # step 2: fill from all of them
r, c = stack.pop()
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == "O":
board[nr][nc] = "S"
stack.append((nr, nc))
for r in range(rows): # step 3: O becomes X, S becomes O
for c in range(cols):
board[r][c] = "O" if board[r][c] == "S" else "X"
board = [list("XXXX"), list("XOOX"), list("XXOX"), list("XOXX")]
capture_surrounded(board)
for row in board:
print("".join(row))Prints the answer to the first sample, one row on each line.
Each row is a list of characters here, because the function changes cells and a Python string cannot be changed.
The three steps are a few passes over a board of at most cells.
Searching against the flow
In Surrounded Regions, each "O" had to know whether it could reach the edge, and one search from the edge answered for all of them. The search could run in that direction because a move between two "O" cells can be taken either way. In the next problem, some moves are allowed in one direction only.
You get a grid of heights. The Pacific Ocean touches the top and left edges and the Atlantic touches the bottom and right edges. Rain flows from a cell to a side neighbor whose height is less than or equal to its own, and from any edge cell into the ocean beside it. Return every cell from which rain can reach both oceans, in any order.
Constraints
- The grid has rows and columns,
-
heights[r][c]
Sample 1 ยท Input
heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Sample 2 ยท Input
heights = [[1]]
Output
[[0,0]]
The first sample has these heights:
Take the cell (2, 2), with height 5. Rain there can flow to the 3 above it, at (1, 2), and then to the 2 at (0, 2), which is on the top edge, so it reaches the Pacific. It can also flow to the 3 on its right, at (2, 3), and on to the 1 at (2, 4), on the right edge, so it reaches the Atlantic, and (2, 2) is in the answer.
The corner (0, 0), with height 1, is on the Pacific's edge, but its two neighbors have heights 2 and 3, and rain does not flow to a higher cell. Its rain cannot reach the Atlantic, so (0, 0) is not in the answer.
The direct method runs one search from every cell. Each search follows the rain downhill and records which oceans it reaches. One search can visit most of the grid, and there are as many searches as cells. For the largest grid:
That is sixteen times the steps of a one-second budget, so we search from the oceans instead. A fill starts from every cell on the top and left edges, and it moves from a cell to a neighbor that is at least as high.
Each such move is a step of the rain taken backwards: when the fill goes from a cell of height 2 to a neighbor of height 3, rain can flow from the 3 down to the 2. So a cell that the fill marks has a route down to the Pacific, which is the fill's own route in reverse. And a cell with a route down to the Pacific gets marked, because the fill can climb that route from the edge.
A second fill from the bottom and right edges marks the cells whose rain reaches the Atlantic. The answer is the cells marked by both.
DIRECTIONS = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def climb(heights, starts):
rows, cols = len(heights), len(heights[0])
seen = [[False] * cols for _ in range(rows)]
for r, c in starts:
seen[r][c] = True
stack = list(starts)
while stack:
r, c = stack.pop()
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc] and heights[nr][nc] >= heights[r][c]:
seen[nr][nc] = True
stack.append((nr, nc))
return seen
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
top = [(0, c) for c in range(cols)]
left = [(r, 0) for r in range(1, rows)] # (0, 0) is already in top
bottom = [(rows - 1, c) for c in range(cols)]
right = [(r, cols - 1) for r in range(rows - 1)] # the last row is already in bottom
pacific = climb(heights, top + left)
atlantic = climb(heights, bottom + right)
return [[r, c] for r in range(rows) for c in range(cols) if pacific[r][c] and atlantic[r][c]]
print(pacific_atlantic([[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]))
print(pacific_atlantic([[1]]))Prints the seven cells of the first sample in row order, then [[0, 0]].
climb keeps its marks in a seen grid, since the heights must stay as they are. Its only other difference from the fill in Surrounded Regions is the test on the heights at the end of the if. That test is >= and not >, because rain also flows between cells of equal height.
The two fills together mark at most cells, where the direct method took up to steps. The same method applies whenever the question is which cells can reach a given set of target cells: search once from the targets, and take each move backwards.
Fewest moves with breadth-first search
The fills so far would mark the same cells whatever order they took the waiting cells in. A stack, a queue or any other container that hands back what was put in would do, because the fills only had to find which cells are joined. The order matters when the question is the fewest moves between two cells, and the order that answers it is breadth-first search. A queue hands back cells in the order they went in, so every cell one move from the start comes out before any cell two moves away, and each cell is first reached by a shortest route.
On a grid, BFS is the fill with two changes. The stack becomes a queue, and the mark becomes a number: dist[r][c] is the fewest moves from the start to (r, c), and means that the cell has not been reached. When a cell is taken from the queue, each open neighbor that has no distance yet gets that cell's distance plus 1.
Take a grid in which 0 is an open cell and 1 is a wall, and count the moves from the top-left cell to the bottom-right cell:
# for a wall. The start and the goal are highlighted.The bottom-right cell is 5 moves away: right, down, right, right, down. The loop is an ordinary BFS from a single cell, and the practice problem below contains it again.
Worked example
Follow the queue one cell at a time
The trace runs this search on the same grid, one cell per step, and shows the distances as they are filled in. Two of its other presets end with : a grid whose goal cannot be reached, and a grid whose start is a wall.
Expand (0, 0) at distance 0. New neighbours enter the queue once, at the next shortest distance.
- queued
- 1
Change the example input
Current result: 5
Practice: a fill followed by a BFS
A BFS can start from several cells, as the fill in Searching from the border did: every start cell goes into the queue at distance 0 before the loop begins, and each cell then gets its distance to the nearest start. This is called multi-source BFS. The last problem on this page uses it together with a fill, and it is worth trying before you open the solution.
You get an grid of land (1) and water (0) that contains exactly two islands, each a group of land cells joined through shared sides. Return the fewest water cells you must turn into land to join the two islands into one.
Constraints
- Each cell is 0 or 1
- There are exactly two islands
Sample 1 ยท Input
grid = [[0,1],[1,0]]
Output
1
Sample 2 ยท Input
grid = [[0,1,0],[0,0,0],[0,0,1]]
Output
2
Sample 3 ยท Input
grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output
1
In the second sample each island is a single cell, at (0, 1) and (2, 2). Turning (1, 1) and (2, 1) into land joins them. No single water cell is beside both islands, so the answer is 2.
A bridge is a shortest route through water from one island to the other, and it may start at any cell of the first island. A BFS from one land cell finds only the routes that start at that cell, and repeating it from every cell of the island can mean thousands of searches of the same 10,000 cells. A BFS that starts from all the cells of the island at once finds the shortest route in a single search, once a fill has found those cells.
The figure runs both searches on a larger grid, whose islands are (0, 0), (0, 1), (1, 0) and (2, 3), (2, 4), (3, 3):
Solution: a fill of the first island and a BFS from it
- Scan the grid for its first land cell.
- Fill that cell's island. Give every cell of the island distance 0 and put it in the queue.
- Run the BFS from that queue through the water: a water cell reached from a cell at distance gets distance .
- Stop when a cell taken from the queue, at some distance , has a land neighbor with no distance. The answer is .
A land cell with no distance cannot belong to the first island, whose cells all got distance 0 in step 2, so it belongs to the second. The cell beside it at distance is moves out from the first island, and those moves pass through water cells, the cell itself included. Those cells are the bridge. No bridge is shorter, because the queue handed back every cell at a smaller distance earlier, and none of them had the second island beside it.
DIRECTIONS = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def first_land(grid):
n = len(grid)
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
return r, c
def shortest_bridge(grid):
n = len(grid)
dist = [[-1] * n for _ in range(n)]
sr, sc = first_land(grid) # step 1
dist[sr][sc] = 0
stack = [(sr, sc)]
queue = deque()
while stack: # step 2: fill the first island
r, c = stack.pop()
queue.append((r, c))
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1 and dist[nr][nc] == -1:
dist[nr][nc] = 0
stack.append((nr, nc))
while queue: # step 3: spread through the water
r, c = queue.popleft()
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
if grid[nr][nc] == 1:
return dist[r][c] # step 4: the second island
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return -1
print(shortest_bridge([[0, 1], [1, 0]]))
print(shortest_bridge([[0, 1, 0], [0, 0, 0], [0, 0, 1]]))
print(shortest_bridge([[1, 1, 1, 1, 1], [1, 0, 0, 0, 1], [1, 0, 1, 0, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1]]))
print(shortest_bridge([[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0]]))Prints 1, 2 and 1 for the three samples, then 3 for the grid in the figure.
During the fill, dist does the work of seen: a land cell with a distance is a marked cell. The fill and the BFS together give each cell at most one distance, which makes 10,000 cell visits for the largest grid.
Common mistakes
Testing a row against the number of columns.
- Where it breaks
- On the one-row grid
["101"], the testnr < colsaccepts row 1, and the program reads a row that does not exist. A square grid hides the bug, because its two sizes are equal. - The fix
- Compare
nrwith the number of rows andncwith the number of columns.
Changing every
"O"that is not on the edge.- Where it breaks
- On the board
XXX,XOO,XXX, the middle cell is joined to the"O"on the right edge and must stay, but this shortcut turns it into"X". - The fix
- Fill from the edge first. Only an
"O"that the fill does not reach is surrounded.
Taking cells from a stack when the answer is a distance.
- Where it breaks
- On an open grid of 5 rows and 3 columns, the bottom-right cell is 6 moves from the top-left cell. The same search with a stack in place of the queue gives it distance 10.
- The fix
- Use a queue whenever the answer is a number of moves.
Starting the BFS from one cell of the island.
- Where it breaks
- On the third Shortest Bridge sample, a BFS that starts at (0, 0) alone finds the land cell (1, 0) beside it, which has no distance, and returns 0. The answer is 1.
- The fix
- Fill the whole first island before the BFS begins, so that all of its cells have distance 0.
Recall How would you find the size of the largest island instead of the number of islands?
Keep the scan and the fill, and have each fill return how many cells it marked: 1 for the starting cell, and 1 more at every push. The scan keeps the largest of these counts. On the second Number of Islands sample the three fills mark 4, 1 and 2 cells, so the answer is 4.
Further reading
- USACO Guide, SilverFlood Fill(opens in a new tab)
The recursive fill drawn step by step, then CSES Counting Rooms solved with a stack, and a way to pad the grid so that Python can skip the bounds tests.
- Red Blob GamesGrids and Graphs(opens in a new tab)
Builds a grid's nodes and a
neighborsfunction from the same four offsets, then compares three ways to model walls: remove nodes, remove edges or give edges infinite weight. - Red Blob Games, Amit PatelFlow Field Pathfinding for Tower Defense(opens in a new tab)
Runs one breadth-first search from the goal so that every cell learns its distance and its next step, the turn Pacific Atlantic makes, and handles several goals with one extra node.
- Jeff Erickson (PDF)Algorithms, Chapter 5: Basic graph algorithms(opens in a new tab)
Section 5.5 proves that a graph search marks exactly the vertices reachable from its start, whatever container holds the waiting vertices; section 5.6 counts components with one search per unmarked vertex; and section 5.7 runs a flood fill on a grid of pixels without building the graph. Parts of this page adapt this chapterโs text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.