best bridge solution

best_bridge.py

# Write a function, best_bridge, that takes in a grid as an argument. 
# The grid contains water (W) and land (L). There are exactly two islands in the grid. 
# An island is a vertically or horizontally connected region of land. 
# Return the minimum length bridge needed to connect the two islands. 
# A bridge does not need to form a straight line.

from collections import deque
def explore_first_island(r, c, grid):
  rows = len(grid)
  cols = len(grid[0])
  island_positions = set()

  def dfs(r, c):
    if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == 'W' or (r, c) in island_positions:
      return
  
    island_positions.add((r, c))
    
    dfs(r + 1, c)
    dfs(r - 1, c)
    dfs(r, c + 1)
    dfs(r, c - 1)
  
  dfs(r, c)
  return island_positions

def find_shorted_path(first_island, grid):
  rows = len(grid)
  cols = len(grid[0])
  min_dis = float('inf')
  visited = set()
  q = deque()
  
  for r, c in first_island:
    q.append((r + 1, c, 0))
    q.append((r - 1, c, 0))
    q.append((r, c + 1, 0))
    q.append((r, c - 1, 0))
    
  while q:
    i, j, distance = q.popleft()

    if i < 0 or j < 0 or i >= rows or j >= cols or (i, j) in first_island or (i, j) in visited:
      continue

    visited.add((i, j))

    if grid[i][j] == 'L':
      return distance
    else:
      distance += 1
      q.append((i + 1, j, distance)) 
      q.append((i - 1, j, distance))
      q.append((i, j + 1, distance)) 
      q.append((i, j - 1, distance))               
    
def best_bridge(grid):
  rows = len(grid)
  cols = len(grid[0])
  first_island = set()
  
  for r in range(rows):
    if first_island:
      break
      
    for c in range(cols):
      if grid[r][c] == 'L':
        first_island = explore_first_island(r, c, grid)
        break
  
  return find_shorted_path(first_island, grid)

# Test case
grid1 = [
  ["W", "W", "W", "L", "L"],
  ["L", "L", "W", "W", "L"],
  ["L", "L", "L", "W", "L"],
  ["W", "L", "W", "W", "W"],
  ["W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W"],
]

grid2 = [
  ["W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W"],
  ["L", "L", "W", "W", "L"],
  ["W", "L", "W", "W", "L"],
  ["W", "W", "W", "L", "L"],
  ["W", "W", "W", "W", "W"],
]

grid3 = [
  ["W", "W", "W", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "L", "W", "W"],
  ["W", "W", "W", "W", "L", "L", "W", "W"],
  ["W", "W", "W", "W", "L", "L", "L", "W"],
  ["W", "W", "W", "W", "W", "L", "L", "L"],
  ["L", "W", "W", "W", "W", "L", "L", "L"],
  ["L", "L", "L", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "W", "W", "W"],
]

grid4 = [
  ["L", "L", "L", "L", "L", "L", "L", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "L", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "W", "W", "W", "W", "W", "W", "L"],
  ["L", "L", "L", "L", "L", "L", "L", "L"],
]

grid5 = [
  ["W", "L", "W", "W", "W", "W", "W", "W"],
  ["W", "L", "W", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "W", "W", "W"],
  ["W", "W", "W", "W", "W", "W", "L", "W"],
  ["W", "W", "W", "W", "W", "W", "L", "L"],
  ["W", "W", "W", "W", "W", "W", "W", "L"],
]

print(best_bridge(grid1))
print(best_bridge(grid2))
print(best_bridge(grid3))
print(best_bridge(grid4))
print(best_bridge(grid5))