934. Shortest Bridge

934. Shortest Bridge

Tag: Depth-First-Search Breadth-First-Search Manhattan Distance

Difficulty: Medium

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

---

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 1

Example 2:

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 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

Constraints:

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.

---

Depth-First Search + Breadth-First Search

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        # Depth-First Search (DFS) to find the 2 islands
        # Breadth-First Search (BFS) to find the shortest path between 2 islands
        ROWS, COLS = len(grid), len(grid[0])
        DIRECTIONS = [(1,0), (0,1), (-1,0), (0,-1)]

        queue = collections.deque()

        def dfs(row, col):
            grid[row][col] = 2
            queue.append((row, col))
            for next_row, next_col in [(row + dx, col + dy) for dx, dy in DIRECTIONS]:
                if not (0 <= next_row < ROWS and 0 <= next_col < COLS and grid[next_row][next_col] == 1):
                    continue
                dfs(next_row, next_col)
        
        for row in range(ROWS):
            for col in range(COLS):
                if grid[row][col] == 1:
                    start_row, start_col = row, col
                    break
        
        dfs(start_row, start_col)

        ans = 0
        while queue:
            curr = collections.deque()
            for row, col in queue:
                for next_row, next_col in [(row + dx, col + dy) for dx, dy in DIRECTIONS]:
                    if not (0 <= next_row < ROWS and 0 <= next_col < COLS):
                        continue
                    if grid[next_row][next_col] == 1:
                        return ans
                    elif grid[next_row][next_col] == 0:
                        curr.append((next_row, next_col))
                        grid[next_row][next_col] = -1
            
            queue = curr
            ans += 1

        return ans

Breadth-First Search

In this approach, we will use the same strategy as in the previous approach, but we will use BFS instead of DFS to search for all cells of island A. Again, we will first traverse grid, take the first land found (assume it is grid[start_row][start_col]) and treat it as a land cell of island A. Then, we BFS over all cells of island A and set their values to 2 to distinguish them from the other island.

Algorithm

1. Iterate over the grid until we find the first land cell, suppose it is grid[start_row][start_col].
2. Create:

• a queue first_island and add grid[start_row][start_col] on island A to it.
• an empty list new_bfs for the next round's search.
• an empty queue second_bfs_queue for searching the distance between two islands later.

3. Iterate over first_island, for each cell grid[row][col], if grid[row][col] = 1 or if the cell is land:

• set grid[row][col] = 2
• add (row, col) to new_bfs for the next round's search.
• add (row, col) to second_bfs_queue for searching over water cells later.

4. If new_bfs is not empty, we set first_island = new_bfs and repeat step 3. Otherwise, move on to step 5. 5.Set distance = 0.
5. Now we start BFS on water cells. While second_bfs_queue is not empty, we create an empty list new_bfs to collect the cells we need to visit in the next round. Iterate over cells in second_bfs_queue, for each cell (row, col):

• if grid[row][col] = 1, it means we have reached the second island, return distance.
• Otherwise, we look for its unvisited water neighbors (cells with value of 0), mark them as -1 and add them to new_bfs.

7. Once the iteration ends, set second_bfs_queue = new_bfs, increment distance by 1, and repeat the step 4.

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        DIRECTIONS = [(1,0), (0,1), (-1,0), (0,-1)]

        def find_land(grid):
            for x, row in enumerate(grid):
                for y, val in enumerate(row):
                    if val:
                        return (x, y)
        
        start_x, start_y = find_land(grid)
        first_island = collections.deque([(start_x, start_y)])
        queue = collections.deque([(start_x, start_y)])
        visited = defaultdict(lambda:False, dict())
        visited[(start_x, start_y)] = True

        while first_island:
            row, col = first_island.popleft()
            for dx, dy in DIRECTIONS:
                next_row, next_col = dx + row, dy + col
                if not (0 <= next_row < ROWS and 0 <= next_col < COLS and grid[next_row][next_col] and not visited[(next_row, next_col)]):
                    continue
                first_island.append((next_row, next_col))
                queue.append((next_row, next_col))
                visited[(next_row, next_col)] = True
            
        ans = 0
        while queue:
            size = len(queue)
            for i in range(size):
                row, col = queue.popleft()
                for dx, dy in DIRECTIONS:
                    next_row, next_col = row + dx, col + dy
                    if not (next_row in range(ROWS) and next_col in range(COLS) and not visited[(next_row, next_col)]):
                        continue
                    if grid[next_row][next_col]:
                        return ans
                    else:
                        queue.append((next_row, next_col))
                        visited[(next_row, next_col)] = True
            ans += 1
        
        return ans

Manhattan Distance

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        # Time Limit Exceeded
        ROWS, COLS = len(grid), len(grid[0])
        DIRECTIONS = [(1,0), (0,1), (-1,0), (0,-1)]

        island_1, island_2 = set(), set()
        visited = set()
        second = False

        def dfs(row, col, land):
            if not (0 <= row < ROWS and 0 <= col < COLS):
                return
            visited.add((row, col))
            land.add((row, col))
            for next_row, next_col in [(row + dx, col + dy) for dx, dy in DIRECTIONS]:
                if not (0 <= next_row < ROWS and 0 <= next_col < COLS and not (next_row, next_col) in visited and grid[next_row][next_col] == 1):
                    continue
                dfs(next_row, next_col, land)
        
        for row in range(ROWS):
            for col in range(COLS):
                if not (row, col) in visited and grid[row][col] == 1:
                    if not second:
                        dfs(row, col, island_1)
                        second = True
                    else:
                        dfs(row, col, island_2)

        ans = float("inf")
        for p1 in island_1:
            for p2 in island_2:
                # Calculate Manhattan distance
                distance = abs(p2[0] - p1[0]) + abs(p2[1] - p1[1])
                ans = min(distance, ans)
        
        return ans - 1