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].length2 <= n <= 100grid[i][j] is either 0 or 1.- There are exactly two islands in
grid.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
n = len(grid)
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def find_island() -> Tuple[int, int]:
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
return i, j
return -1, -1
def dfs(i: int, j: int, q: List[Tuple[int, int]]) -> None:
grid[i][j] = -1
# add to q, used by BFS
q.append((i, j))
for dx, dy in DIRS:
x, y = i + dx, j + dy
if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:
dfs(x, y, q)
step = 0
q = []
ix, iy = find_island()
dfs(ix, iy, q)
# expand the found island using BFS
while q:
temp_q = []
for i, j in q:
for dx, dy in DIRS:
x, y = i + dx, j + dy
if 0 <= x < n and 0 <= y < n:
if grid[x][y] == 1:
return step
elif grid[x][y] == 0:
grid[x][y] = -1
temp_q.append((x, y))
step += 1
q = temp_q
return -1
|