leetcode - 934. Shortest Bridge

Description

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.

Solution

Use DFS to find one island, then use BFS to expand the island, until it meets another island.

Time complexity: $o(m?n)$
Space complexity: $o(m?n)$

Code

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        def dfs(x: int, y: int, island: list) -> None:
            stack = [(x, y)]
            while stack:
                x, y = stack.pop()
                if (x, y) in island:
                    continue
                island.append((x, y))
                for dz in (-1, 1):
                    if 0 <= x + dz < m and grid[x + dz][y] == 1:
                        stack.append((x + dz, y))
                    if 0 <= y + dz < n and grid[x][y + dz] == 1:
                        stack.append((x, y + dz))

        # get the 1s of an island
        # [(x1, y1), (x2, y2), ...]
        island = []
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    dfs(i, j, island)
                    break
            if island:
                break
        # BFS
        queue = collections.deque([(x, y, 0) for x, y in island])
        visited = set()
        while queue:
            x, y, step = queue.popleft()
            if (x, y) in visited:
                continue
            visited.add((x, y))
            if grid[x][y] == 0:
                grid[x][y] = 1
                island.append((x, y))
            elif (x, y) not in island:
                return step
            for dz in (-1, 1):
                if 0 <= x + dz < m and (x + dz, y) not in island:
                    next_step = step + (1 if grid[x + dz][y] == 0 else 0)
                    queue.append((x + dz, y, next_step))
                if 0 <= y + dz < n and (x, y + dz) not in island:
                    next_step = step + (1 if grid[x][y + dz] == 0 else 0)
                    queue.append((x, y + dz, next_step))