难度：★★★★☆
类型：数组
方法：深度优先搜索，宽度优先搜索

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

在给定的二维二进制数组 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 <= 100
A[i][j] == 0 或 A[i][j] == 1

解答

这类问题在二维数组的搜索方式中算比较复杂了，最重要的是理清思路。

比较容易理解的方法是：

第一步：我们可以找到两座岛屿，并将组成这两座岛屿的坐标点保存在两个集合中。这一步，我们很容易使用深度优先搜索实现。

第二步，以其中一个岛屿为基础，向外填海造陆，直到与另一座岛屿相切，这时，我们就可以记录用了多少圈，从而找到最短的桥的长度。这一步，我们使用宽度优先搜索。

我们将两步写成功能函数，实现岛屿搜寻通过递归的深度优先搜索，对于填海造陆的过程，使用队列进行逐点遍历，每个点不仅包含位置信息，还需要包含深度信息，也就是当前已经扩充到了第几圈。

以下几点需要留意：

1. 获取周围点的坐标时，及时判断点的位置是否合法；
2. 使用集合记录遍历过的位置，避免重复的计算开销；
3. 递归调用时注意返回值的更新；

class Solution:

    def get_islands(self, A):

        def dfs(r, c, res:set):
            if (r, c) not in seen and 0 <= r < len(A) and 0 <= c < len(A[0]) and A[r][c]:
                res.add((r, c))
                seen.add((r, c))
                for nr, nc in [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)]:
                    dfs(nr, nc, res)
                return res

        islands = []
        seen = set()

        for r in range(len(A)):
            for c in range(len(A[0])):
                if (r, c) not in seen and A[r][c]:
                    islands.append(dfs(r, c, set()))
                seen.add((r, c))
        return islands

    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

        island_1, island_2 = self.get_islands(A)
        queue = [(node, 0) for node in island_1]
        done = set(island_1)

        while queue:
            location, depth = queue.pop(0)
            if location in island_2:
                return depth-1
            for nei in neighbors(*location):
                if nei not in done:
                    queue.append((nei, depth+1))
                    done.add(nei)

s = Solution()
A = [[1, 1, 0, 0, 0, 0],
     [1, 1, 1, 0, 0, 0],
     [1, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0],
     [0, 0, 0, 1, 0, 0],
     [0, 0, 0, 1, 1, 0],
     [0, 0, 0, 0, 0, 0],
     ]
# print(s.get_islands(A))
print(s.shortestBridge(A))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析