美文网首页
934. 最短的桥(Python)

934. 最短的桥(Python)

作者: 玖月晴 | 来源:发表于2021-03-30 16:12 被阅读0次

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

    题目

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

    在给定的二维二进制数组 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解决方案,请移步力扣中等题解析

    相关文章

      网友评论

          本文标题:934. 最短的桥(Python)

          本文链接:https://www.haomeiwen.com/subject/qzlpqltx.html