文章作者：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 = Falsefor j in range(n):if grid[i][j] == 1:grid[i][j] = 2queue.append((i, j))flag = Truebreakif flag:breakwhile queue:x, y = queue.popleft()queue2.append((x, y, 0))if x > 0 and grid[x-1][y] == 1:grid[x-1][y] = 2queue.append((x-1, y))if y > 0 and grid[x][y-1] == 1:grid[x][y-1] = 2queue.append((x, y-1))if x < n-1 and grid[x+1][y] == 1:grid[x+1][y] = 2queue.append((x+1, y))if y < n-1 and grid[x][y+1] == 1:grid[x][y+1] = 2queue.append((x, y+1))while queue2:x, y, count = queue2.popleft()if x > 0:if grid[x-1][y] == 0:grid[x-1][y] = 2queue2.append((x-1, y, count + 1))elif grid[x-1][y] == 1:return countif y > 0:if grid[x][y-1] == 0:grid[x][y-1] = 2queue2.append((x, y-1, count + 1))elif grid[x][y-1] == 1:return countif x < n-1:if grid[x+1][y] == 0:grid[x+1][y] = 2queue2.append((x+1, y, count + 1))elif grid[x+1][y] == 1:return countif y < n-1:if grid[x][y+1] == 0:grid[x][y+1] = 2queue2.append((x, y+1, count + 1))elif grid[x][y+1] == 1:return count
Reference
- https://leetcode.com/problems/shortest-bridge/