文章作者：Tyan 博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
**解析：**Version 1，先找到矩阵中第一个1作为起点，然后使用广度优先搜索找到所有相邻的1，即第一个岛，并将所有岛的坐标及更改的0计数保存到队列中，初始计数为0，搜索第一个岛的同时，将各个点对应的值设为2，防止重复搜索。从第一个岛的所有点开始，重新使用广度优先搜索，如果搜索的点值为0，将值设为2，表示已经搜索过，同时将点的坐标及计数保存，计数要加1，如果搜索的点为1，说明找到了第二个岛，返回反转的0的计数。
- Version 1
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
n = len(grid)
queue = collections.deque()
queue2 = collections.deque()
for i in range(n):
flag = False
for j in range(n):
if grid[i][j] == 1:
grid[i][j] = 2
queue.append((i, j))
flag = True
break
if flag:
break
while queue:
x, y = queue.popleft()
queue2.append((x, y, 0))
if x > 0 and grid[x-1][y] == 1:
grid[x-1][y] = 2
queue.append((x-1, y))
if y > 0 and grid[x][y-1] == 1:
grid[x][y-1] = 2
queue.append((x, y-1))
if x < n-1 and grid[x 1][y] == 1:
grid[x 1][y] = 2
queue.append((x 1, y))
if y < n-1 and grid[x][y 1] == 1:
grid[x][y 1] = 2
queue.append((x, y 1))
while queue2:
x, y, count = queue2.popleft()
if x > 0:
if grid[x-1][y] == 0:
grid[x-1][y] = 2
queue2.append((x-1, y, count 1))
elif grid[x-1][y] == 1:
return count
if y > 0:
if grid[x][y-1] == 0:
grid[x][y-1] = 2
queue2.append((x, y-1, count 1))
elif grid[x][y-1] == 1:
return count
if x < n-1:
if grid[x 1][y] == 0:
grid[x 1][y] = 2
queue2.append((x 1, y, count 1))
elif grid[x 1][y] == 1:
return count
if y < n-1:
if grid[x][y 1] == 0:
grid[x][y 1] = 2
queue2.append((x, y 1, count 1))
elif grid[x][y 1] == 1:
return countReference
- https://leetcode.com/problems/shortest-bridge/
