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.
- code
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
def dfs(x, y):
grid[x][y] = 2
for dx, dy in d:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] == 1: dfs(nx, ny)
elif grid[nx][ny] == 0:
q.add((nx, ny))
m, n = len(grid), len(grid[0])
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = set()
for i, j in product(range(m), range(n)):
if grid[i][j] == 1:
dfs(i, j) # paint one island to 2, border 0 add to q
break
step = 0
q = deque(q)
while q:
for _ in range(len(q)):
x, y = q.popleft()
if grid[x][y] == 1: return step
for dx, dy in d:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != 2:
if grid[nx][ny] == 0: grid[nx][ny] = 2 # mark visited
q.append((nx, ny))
step += 1
return step
- code
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
def dfs(x, y):
grid[x][y] = 2
for dx, dy in d:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] == 1: dfs(nx, ny)
elif grid[nx][ny] == 0:
q.add((nx, ny))
m, n = len(grid), len(grid[0])
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = set()
for i, j in product(range(m), range(n)):
if grid[i][j] == 1:
dfs(i, j) # paint one island to 2, border 0 add to q
break
step = 0
q = deque(q)
while q:
for _ in range(len(q)):
x, y = q.popleft()
for dx, dy in d:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] == 1: return step + 1
if grid[nx][ny] == 0:
grid[nx][ny] = 2 # mark visited
q.append((nx, ny))
step += 1
return step