Shortest Bridge

class Solution: def shortestBridge(self, grid: List[List[int]]) -> int: # Initialize variables visited = set() nrows, ncols = len(grid), len(grid[0]) # Define getNeighbours function def getNeighbors(r, c): neighbors = [] for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = r + dr, c + dc if nr >= 0 and nr < nrows and nc >= 0 and nc < ncols: neighbors.append((nr, nc)) return neighbors # Define DFS function def dfs(r, c): if (r, c) not in visited and grid[r][c] == 1: visited.add((r, c)) for nr, nc in getNeighbors(r, c): dfs(nr, nc) # Define BFS function def bfs(r, c): numberOfBFSs = 0 queue = deque(visited) while queue: for _ in range(len(queue)): r, c = queue.popleft() for nr, nc in getNeighbors(r, c): if (nr, nc) not in visited: if grid[nr][nc] == 1: return numberOfBFSs queue.append((nr, nc)) visited.add((nr, nc)) numberOfBFSs += 1 return numberOfBFSs # Conduct DFS to find first island for r in range(nrows): for c in range(ncols): if grid[r][c] == 1: dfs(r, c) return bfs(r, c) return 0