难度: Medium
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
示例 1：
输入：grid = [[0,1],[1,0]] 输出：1
示例 2：
输入：grid = [[0,1,0],[0,0,0],[0,0,1]] 输出：2
示例 3：
输入：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]] 输出：1
提示：
n == grid.length == grid[i].length2 <= n <= 100grid[i][j] 为 0 或 1grid 中恰有两个岛运行时间: 61 ms
内存: 16.8 MB
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
dir = ((0, 1), (1, 0), (0, -1), (-1, 0))
n, m = len(grid), len(grid[0])
# 先随便找一个岛
st = list()
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == 1:
st.append((i, j))
grid[i][j] = -1
break
if st: break
# 扩展全岛入队
p = 0
while p < len(st):
i, j = st[p]
for dx, dy in dir:
x, y = i + dx, j + dy
if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] != 1:
continue
st.append((x, y))
grid[x][y] = -1
p += 1
# 多源 BFS 找最短路
for step in range(n * m + 1):
st2 = list()
for i, j in st:
for dx, dy in dir:
x, y = i + dx, j + dy
if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] == -1:
continue
if grid[x][y] == 1:
return step
st2.append((x, y))
grid[x][y] = -1
st = st2
return -1
题解的核心思路是使用广度优先搜索（BFS）来找到连接两座岛屿的最短桥。首先，通过遍历矩阵来找到第一个岛屿，并使用一个队列标记所有属于这个岛屿的坐标，同时将这些位置在grid中标记为-1以表示已访问。接着，使用多源BFS从第一个岛屿的所有位置开始扩展，搜索最短的路径到第二个岛屿。每扩展一层，步数增加1，如果遇到未访问的陆地（值为1），则返回当前步数，这表示找到了第二个岛屿，且当前步数即为需要翻转的最小0的数量。
时间复杂度: O(n*m)
空间复杂度: O(n*m)
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
dir = ((0, 1), (1, 0), (0, -1), (-1, 0))
n, m = len(grid), len(grid[0])
# 先随便找一个岛
st = list()
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == 1:
st.append((i, j))
grid[i][j] = -1
break
if st: break
# 扩展全岛入队
p = 0
while p < len(st):
i, j = st[p]
for dx, dy in dir:
x, y = i + dx, j + dy
if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] != 1:
continue
st.append((x, y))
grid[x][y] = -1
p += 1
# 多源 BFS 找最短路
for step in range(n * m + 1):
st2 = list()
for i, j in st:
for dx, dy in dir:
x, y = i + dx, j + dy
if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] == -1:
continue
if grid[x][y] == 1:
return step
st2.append((x, y))
grid[x][y] = -1
st = st2
return -1
在解决最短桥问题时，选择第一个遇到的岛屿作为起点是基于实现的简便性而非最优性。算法的目标是找到两个岛屿之间的最短路径，而不依赖于起始岛屿的选择。因此，无论从哪个岛屿开始，只要能正确识别两个岛屿并执行多源BFS，最终都能找到最短的桥。
BFS算法通过队列来保持扩展的顺序，遵循先进先出（FIFO）的原则。因此，首先遇到的边缘位置会首先被扩展。在多源BFS的情况下，所有当前步骤中可扩展的位置都将被同时加入队列，并在下一步骤中统一处理，这确保了搜索的层次性和公平性。
选择`n * m + 1`作为循环上限是一种保守的设计，确保在极端情况下算法仍能运行完全。理论上，最短桥的长度不会超过网格的大小，但在实践中，通常不会需要这么多步骤。这个上限考虑了所有可能的位置都必须至少被访问一次的最糟情况。
为了减少重复工作，可以在加入新位置到队列前，检查该位置是否已被访问或已经在队列中。通常，可以通过设置一个额外的状态数组或修改原地图的值来标记已经访问的位置。此外，使用集合代替队列来存储待扩展的位置也是一种方法，尽管这可能增加了空间复杂度，但可以有效避免重复扩展同一位置。