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\ast n)$
Space complexity: $o(m\ast 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:continueisland.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)breakif island:break# BFSqueue = collections.deque([(x, y, 0) for x, y in island])visited = set()while queue:x, y, step = queue.popleft()if (x, y) in visited:continuevisited.add((x, y))if grid[x][y] == 0:grid[x][y] = 1island.append((x, y))elif (x, y) not in island:return stepfor 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))