Skip to content

934. Shortest Bridge

Difficulty Topics

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

shortest-bridge.py
class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()

        def dfs(x, y):
            grid[x][y] = -1
            queue.append((x, y))

            for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if 0 <= dx < rows and 0 <= dy < cols and grid[dx][dy] == 1:
                    dfs(dx, dy)

        flag = False
        for x in range(rows):
            for y in range(cols):
                if grid[x][y] == 1:
                    flag = True
                    dfs(x, y)
                    break

            if flag: break

        steps = 0
        while queue:
            n = len(queue)

            for _ in range(n):
                x, y = queue.popleft()

                for dx, dy in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if 0 <= dx < rows and 0 <= dy < cols and grid[dx][dy] != -1:
                        if grid[dx][dy] == 1: return steps
                        queue.append((dx, dy))
                        grid[dx][dy] = -1

            steps += 1

        return -1