934. Shortest Bridge

Problem Link

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

---

Python3

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        bfs = deque()
 
        def color(x, y):
            grid[x][y] = 2
            bfs.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:
                    color(dx, dy)
        
        for i in range(rows):
            flag = False
            for j in range(cols):
                if grid[i][j] == 1:
                    color(i, j)
                    flag = True
                    break
            
            if flag: break
 
        res = 0
 
        while bfs:
            N = len(bfs)
            
            for _ in range(N):
                x, y = bfs.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 res
 
                        grid[dx][dy] = -1
                        bfs.append((dx, dy))
 
            res += 1
 
        return -1