LeetCode每日一题——934. 最短的桥

简介: 给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地,0 表示水域。

题目

给你一个大小为 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

思路

思路简单这里采用深度优先搜索+广度优先搜索,但是做起来比较麻烦。

我们可以利用深度优先搜索求出其中的一座岛,然后利用广度优先搜索来找到两座岛的最短距离。深度度优先搜索时,我们可以将已经遍历过的位置标记为 −1,实际计算过程如下:

  • 我们通过遍历找到数组 grid中的 1 后进行深度优先搜索,此时可以得到第一座岛的位置集合,记为 island,并将其位置全部标记为 −1。
  • 随后我们从 island 中的所有位置开始进行广度优先搜索,当它们到达了任意的 1时,即表示搜索到了第二个岛,搜索的层数就是答案。

题解

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v != 1:
                    continue
                q = []
                def dfs(x: int, y: int) -> None:
                    grid[x][y] = -1
                    q.append((x, y))
                    for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                            dfs(nx, ny)
                dfs(i, j)
                step = 0
                while True:
                    tmp = q
                    q = []
                    for x, y in tmp:
                        for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
                            if 0 <= nx < n and 0 <= ny < n:
                                if grid[nx][ny] == 1:
                                    return step
                                if grid[nx][ny] == 0:
                                    grid[nx][ny] = -1
                                    q.append((nx, ny))
                    step += 1
目录
相关文章
|
Java Windows
学习 Java 安装过程
学习 Java 安装过程
99 0
|
SQL 数据采集 关系型数据库
大数据采集和抽取怎么做?这篇文章终于说明白了!
数据是数据中台\数据平台核心中的核心,因此数据汇聚必然是数据中台/平台的入口,本文详细讲述采集模块的方方面面、采集框架的使用选型以及企业真实落地
大数据采集和抽取怎么做?这篇文章终于说明白了!
|
人工智能 Java 数据库连接
ResourceManager unable to find resource .
# Mybatis Velocity模板引擎问题详解 当遇到`ResourceManagerException`无法找到资源时,可能原因包括:资源路径不正确、未正确加载文件、编码不一致或Velocity配置错误。解决方案包括:检查并修正资源文件路径、确保资源文件加载配置、统一文件编码和审查Velocity引擎配置。详细步骤和配置示例见原文。[阅读完整文章以获取更多帮助](&lt;!-- article_link --&gt;)。我是木头左,和你一起探索AI世界!
 ResourceManager unable to find resource .
|
6月前
|
人工智能 文字识别 计算机视觉
HarmonyOS NEXT AI基础视觉服务-文字识别
本案例展示了一款基于AI基础视觉服务的文字识别应用,通过调用设备相机拍摄照片并识别图片中的文字内容。主要实现步骤包括:1) 导入所需功能模块;2) 调用相机获取图片URI;3) 将图片转换为可识别的像素图;4) 配置视觉识别参数并执行文字识别;5) 构建界面组件,实现拍照与结果显示交互。核心要点涵盖相机权限、图像格式兼容及结构化识别结果处理,完整代码整合了各功能模块的调用流程,确保功能顺畅运行。
|
弹性计算 Ubuntu Linux
阿里云服务器的镜像是什么?操作系统选择看这篇就够了!
阿里云服务器镜像是服务器的“装机盘”,用于安装操作系统、初始化应用数据和预装软件。镜像分公共、自定义、共享、云市场和社区镜像。公共镜像为官方提供,含正版授权;自定义镜像由用户创建;共享镜像由其他账户共享;云市场镜像含预装软件;社区镜像由用户公开发布。操作系统选择取决于应用场景,推荐Linux选Alibaba Cloud Linux,Windows选2022数据中心版。低配服务器推荐Linux以节省资源。64位操作系统优于32位。中国大陆地域服务器支持免费无限次更换操作系统,非中国大陆地域有限制。Alibaba Cloud Linux由阿里云推出,针对ECS优化,兼容RHEL/CentOS生态。
1612 14
|
Ubuntu Unix Linux
Unix/Linux操作系统的最强入门科普(经典)
Unix/Linux操作系统的最强入门科普(经典)
786 0
|
存储 Python
逆天改命?Python元类:从菜鸟到大师,一键升级你的编程认知
【7月更文挑战第6天】Python的元类是类的构造器,允许控制类的创建。元类`Meta`通过`__new__`方法动态添加属性,如示例所示,创建`MyClass`时添加`new_attr`。元类还能实现高级功能,如单例模式,`SingletonMeta`元类确保同一类的所有实例相等。元类是进阶技术,能提升代码的灵活性和创造力。
81 0
|
C++ 容器
【C++初阶】STL详解(六)Stack与Queue的介绍与使用
【C++初阶】STL详解(六)Stack与Queue的介绍与使用
130 1
|
SQL 前端开发 JavaScript
Node第三方包 【mysql2】
Node第三方包 【mysql2】
594 0
剑指 Offer 56 - II:数组中数字出现的次数 II
剑指 Offer 56 - II:数组中数字出现的次数 II
84 0