934. Shortest Bridge
Đề Bài
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 either0or1.- There are exactly two islands in
grid.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(V+E)
💾 Không gian
O(V)
Lời Giải
Python
0934-shortest-bridge.py
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
DIR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
n = len(grid)
def isValid(x: int, y: int) -> bool:
return 0 <= x < n and 0 <= y < n
dq = deque()
def dfs(x: int, y: int) -> None:
if not isValid(x, y) or grid[x][y] in (0, 2):
return
grid[x][y] = 2
dq.append((x, y))
for dx, dy in DIR:
dfs(x + dx, y + dy)
flag = False
for x in range(n):
for y in range(n):
if grid[x][y] == 1 and not flag:
flag = True
dfs(x, y)
break
if flag:
break
dist = 0
while dq:
sz = len(dq)
for _ in range(sz):
x, y = dq.popleft()
for dx, dy in DIR:
nx = x + dx
ny = y + dy
if isValid(nx, ny):
if grid[nx][ny] == 1:
return dist
elif grid[nx][ny] == 0:
dq.append((nx, ny))
grid[nx][ny] = 2
dist += 1
return -1