A grid contains exactly two islands of land (L) separated by water (W).
Return the minimum number of water cells you must turn into land to connect the two
islands (the length of the shortest bridge).
bestBridge(grid)
Input format: rows separated by |.
LWL // → 1
LWWL // → 2
LL|WW|LL // → 1
This looks intimidating, but it decomposes into two techniques you've already built: flood-filling an island, and BFS for shortest distance across water. The trick is combining them, adapting the BFS to start from many cells at once.
Scan the grid until you find any land cell — either island works, since both are symmetric. Flood-fill outward exactly as in island counting, but this time collect every cell into a list instead of just marking and discarding. That list is the entirety of "island one," and every cell in it is a valid starting point for reaching island two.
Once you have island one's cells, the question becomes: starting simultaneously from every cell of island one, what's the fewest water-cell steps to reach the other island? Still an unweighted shortest-path question, so BFS is still right — the twist is seeding the queue with the entire first island at distance 0 at once. This is multi-source BFS: since all of island one starts at distance 0, the search measures distance purely in water crossed, not land already owned.
BFS's ring-by-ring expansion holds regardless of how many starting points you seed — it still explores all cells at true distance 1 from any source before distance 2, and so on. So the first time the frontier reaches a land cell not part of the original island (necessarily the second island), the water steps taken is the shortest possible bridge.
Since every cell of island one is already "free" (distance 0), mark them all visited before the BFS begins, so the search doesn't waste time on movement within the first island or re-add its cells to the queue.
from collections import deque
def best_bridge(grid):
rows = len(grid)
cols = len(grid[0])
visited = [[False] * cols for _ in range(rows)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
# Discover the first island.
island = []
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or visited[r][c] or grid[r][c] != "L":
return
visited[r][c] = True
island.append((r, c))
for dr, dc in dirs:
dfs(r + dr, c + dc)
found = False
for r in range(rows):
if found:
break
for c in range(cols):
if grid[r][c] == "L":
dfs(r, c)
found = True
break
# Multi-source BFS from the first island outward.
queue = deque((r, c, 0) for r, c in island)
while queue:
r, c, d = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if nr < 0 or nr >= rows or nc < 0 or nc >= cols or visited[nr][nc]:
continue
if grid[nr][nc] == "L":
return d
visited[nr][nc] = True
queue.append((nr, nc, d + 1))
return -1
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.