class Solution {
public:
int shortestBridge(vector<vector<int>>& grid) {
}
};
934. 最短的桥
在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）
示例 1：
输入：A = [[0,1],[1,0]] 输出：1
示例 2：
输入：A = [[0,1,0],[0,0,0],[0,0,1]] 输出：2
示例 3：
输入：A = [[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]] 输出：1
提示：
2 <= A.length == A[0].length <= 100A[i][j] == 0 或 A[i][j] == 1原站题解
python3 解法, 执行用时: 100 ms, 内存消耗: 15.4 MB, 提交时间: 2022-08-01 10:42:25
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
# 01BFS 先找到一个整体的1 然后再探查另一个岛上的1
from collections import deque
m = len(grid)
n = len(grid[0])
visit = [[False] * n for _ in range(m)]
def bfs(i,j):
queue = deque([(i,j,0)])
while queue:
xx,yy,time = queue.popleft()
for dx,dy in ((xx+1,yy),(xx-1,yy),(xx,yy+1),(xx,yy-1)):
if dx>=0 and dx < m and dy >= 0 and dy < n and visit[dx][dy] == False:
visit[dx][dy] = True
if grid[dx][dy] == 1:
# time >= 1 表示通过跨越0 找到另一个岛了
if time >= 1:
return time
else:
# time为0表示此时还是在同一个岛屿，记得左插，优先级大于0的块
queue.appendleft((dx,dy,0))
else:
queue.append((dx,dy,time+1))
# 找到第一个为1的点
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
visit[i][j] = True
return bfs(i,j)
python3 解法, 执行用时: 260 ms, 内存消耗: 16.4 MB, 提交时间: 2022-08-01 10:41:47
class Solution(object):
def shortestBridge(self, A):
R, C = len(A), len(A[0])
def neighbors(r, c):
for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
def get_components():
done = set()
components = []
for r, row in enumerate(A):
for c, val in enumerate(row):
if val and (r, c) not in done:
# Start dfs
stack = [(r, c)]
seen = {(r, c)}
while stack:
node = stack.pop()
for nei in neighbors(*node):
if A[nei[0]][nei[1]] and nei not in seen:
stack.append(nei)
seen.add(nei)
done |= seen
components.append(seen)
return components
source, target = get_components()
queue = collections.deque([(node, 0) for node in source])
done = set(source)
while queue:
node, d = queue.popleft()
if node in target: return d-1
for nei in neighbors(*node):
if nei not in done:
queue.append((nei, d+1))
done.add(nei)