[LeetCode] 695. 岛屿的最大面积

题目描述:

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。

示例 1:

输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出:6
解释:答案不应该是11,因为岛屿只能包含水平或垂直这四个方向上的1。

示例 2:

输入:grid = [[0,0,0,0,0,0,0,0]]
输出:0

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 为 0 或 1

题目链接:

. - 力扣(LeetCode)

解题主要思路:

这题同样是 “渲染图像” 升级而来的,跟 “岛屿数量” 那道题基本没差别,会 “岛屿数量” 那道题就肯定会这题。一块岛屿无非就是调用一次 "图像渲染",但是比如说有三块岛屿,我找出一块后,如何让这块岛屿不影响另外两块岛屿的搜索呢?很简单,两种方式,一种是当我们找出‘陆地’后,将其改成‘海洋’;另一种方式就是定义一个数组vis,用来记录该元素是否已经被搜索过了,这样的好处就是不会更改原数据。这次我采用第一种解题方式,“岛屿数量” 这道题我提供了两种解法,可以点击下方的链接学习学习。
岛屿数量链接:https://blog.csdn.net/weixin_65043441/article/details/142984279

解题代码:

class Solution {
public:
    typedef pair<int, int> PII;
    int dx[4] {0, 0, 1, -1};
    int dy[4] {1, -1, 0, 0};
    int m, n;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = 0;
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) ret = max(ret, bfs(grid, i, j));
            }
        }
        return ret;
    }
    int bfs(vector<vector<int>>& grid, int r, int c)
    {
        int ret = 1;
        queue<PII> que;
        que.push(make_pair(r, c));
        grid[r][c] = 0;  // 消除影响
        while (que.size()) {
            auto [a, b] = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                    ++ret;
                    que.push(make_pair(x, y));
                    grid[x][y] = 0;  // 消除影响
                }
            }
        }
        return ret;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/893015.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java 小游戏《超级马里奥》

文章目录 一、效果展示二、代码编写1. 素材准备2. 创建窗口类3. 创建常量类4. 创建动作类5. 创建关卡类6. 创建障碍物类7. 创建马里奥类8. 编写程序入口 一、效果展示 二、代码编写 1. 素材准备 首先创建一个基本的 java 项目&#xff0c;并将本游戏需要用到的图片素材 image…

大数据-174 Elasticsearch Query DSL - 全文检索 full-text query 匹配、短语、多字段 详细操作

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…

推荐一个可以免费上传PDF产品图册的网站

​在数字化时代&#xff0c;企业将产品图册以PDF格式上传至网络&#xff0c;不仅便于客户浏览和下载&#xff0c;还能提升企业的专业形象。今天&#xff0c;就为您推荐一个可以免费上传PDF产品图册的网站——FLBOOK&#xff0c;轻松实现产品图册的在线展示。 1.注册登录&#x…

交通目标识别数据集YOLO 模型 ui界面✓图片数量15000,xml和txt标签都有 11类 交通道路车辆行人红黄绿数据集 红绿灯数据集 交通信号数据集

YOLO交通目标识别 数据集 模型 ui界面 ✓图片数量15000&#xff0c;xml和txt标签都有&#xff1b; ✓class&#xff1a;biker&#xff0c;car&#xff0c;pedestrian&#xff0c;trafficLight&#xff0c;trafficLight-Green&#xff0c;trafficLight-GreenLeft&#xff0c; tr…

调用第三方接口

目录 一、分析给出的接口文档 二、请求体格式之间的区别 三、示例代码 一、分析给出的接口文档 一般的接口文档包括以下几大部分&#xff1a; 1、请求URL&#xff1a;http://{ip}:{port}/api/ec/dev/message/sendCustomMessageSingle 2、请求方式&#xff1a;POST、GET等 3、…

3.C++经典实例-奇数还是偶数

要判断一个数是奇数还是偶数&#xff0c;只需要判断这个数是否能被2整除即可&#xff0c;如果要判断是否能整除&#xff0c;则要判断当前数除以2的余数是否为0&#xff0c;在C中&#xff0c;余数&#xff0c;使用%号&#xff0c;因此&#xff0c;程序为&#xff1a; #include …

缓存常见问题:缓存穿透、雪崩、击穿及解决方案分析

1. 什么是缓存穿透&#xff0c;怎么解决&#xff1f; 缓存穿透是指用户请求的数据在缓存中不存在即没有命中&#xff0c;同时在数据库中也不存在&#xff0c;导致用户每次请求该数据都要去数据库中查询一遍。如果有恶意攻击者不断请求系统中不存在的数据&#xff0c;会导致短时…

C++初阶学习第七弹——string的模拟实现

C初阶学习第六弹------标准库中的string类_c语言返回string-CSDN博客 通过上篇我们已经学习到了string类的基本使用&#xff0c;这里我们就试着模拟实现一些&#xff0c;我们主要实现一些常用到的函数。 目录 一、string类的构造 二、string类的拷贝构造 三、string类的析构函…

第十四届单片机嵌入式蓝桥杯

一、CubeMx配置 &#xff08;1&#xff09;LED配置 &#xff08;1&#xff09;LED灯里面用到了SN74HC573ADWR锁存器&#xff0c;这个锁存器有一个LE引脚,这个是我们芯片的锁存引脚&#xff08;使能引脚&#xff09;&#xff0c;由PD2这个端口来控制的 &#xff08;2&#xff…

13图书归还-云图书管理系统(Vue3+Spring Boot+element plus)

目录 1 接口地址2 后台代码RecordControllerBookController 3 view/books/BookRecordsVue中前端框架搭建4 api/record.js文件写查询用户借阅记录的接口代码5 api/book.js中写归还图书、查询当前借阅图书接口代码6 BookRecordsVue中导入接口函数&#xff0c;并调用7 运行效果 1 …

C++/初识C++

目录 一、前言 二、正文 1C语言第一个程序&#xff1a; 1.1C的第一个程序&#xff1a; 2.命名空间 2.1 namespace的价值 2.2namespace的定义 2.3namespace的正常使用 3.C输出和输入 三、结言 一、前言 点来不及悼念C语言&#xff0c;接下来出场的是新的语言C。不同于C…

【数据采集工具】Sqoop从入门到面试学习总结

国科大学习生活&#xff08;期末复习资料、课程大作业解析、大厂实习经验心得等&#xff09;: 文章专栏&#xff08;点击跳转&#xff09; 大数据开发学习文档&#xff08;分布式文件系统的实现&#xff0c;大数据生态圈学习文档等&#xff09;: 文章专栏&#xff08;点击跳转&…

unity Gpu优化

不一样的视角&#xff0c;深度解读unity性能优化。unity性能优化&#xff0c;unity内存优化&#xff0c;cpu优化&#xff0c;gpu优化&#xff0c;资源优化&#xff0c;资源包、资源去重优化&#xff0c;ugui优化。 gpu优化静态批处理静态批处理原理规则静态合批的原理静态合批的…

2023年华为杯数学建模竞赛B题论文和代码

DFT类矩阵的整数分解逼近 离散傅里叶变换&#xff08;Discrete Fourier Transform&#xff0c;DFT&#xff09;傅里叶分析方法是信号分析的最基本方法&#xff0c;傅里叶变换是傅里叶分析的核心&#xff0c;通过它把信号从时间域变换到频率域&#xff0c;进而研究信号的频谱结构…

SSM四川工商学院学生宿舍管理系统---附源码54633

摘 要 从20年代开始&#xff0c;计算机疯狂的出现在人们的生活以及工作当中&#xff0c;成为人们生活、工作的好帮手&#xff0c;计算机深入到每家每户当中&#xff0c;网络办公&#xff0c;网络教学更是替换了传统手工记录管理的方式&#xff0c;使用计算机办公可以不必局限于…

MySQL-12.DQL-聚合函数

一.DQL-分组查询 二.聚合函数 -- DQL:分组查询 -- 聚合函数 -- 1.统计该企业员工数量 count select count(id) from tb_emp; select count(job) from tb_emp;select count(A) from tb_emp; select count(*) from tb_emp;-- 2.统计该企业最早入职的员工 min select min(entr…

SQL第18课挑战题

1. 创建一个名为customerswithorders的视图&#xff0c;其中包含customers表中的所有列&#xff0c;但仅仅是那些已下订单的列。提示&#xff1a;可以在orders表上使用join来仅仅过滤所需的顾客&#xff0c;然后使用select来确保用有正确的数据。 创建视图&#xff1a;

电影台词摘抄(十一)——Banana!

Scarlet&#xff1a;Do you know who this is? Kevin&#xff1a;Uh. La cucaracha? n.伊丽莎白(女子名) Scarlet&#xff1a;This is Queen Elizabeth, ruler of England.Oh, I love England, Their music, the …

Linux - 环境变量 | 命令行参数 | 进程基础

文章目录 一、了解冯诺依曼体系结构1、概念2、对数据层面3、实例二、操作系统1、概念2、设计OS的目的3、定位4、操作系统怎么管理&#xff1f; 三、进程1、概念2、怎么管理进程3、描述进程-PCB4、描述进程怎么运行&#xff08;粗略&#xff09;5、进程属性6、创建子进程7、创建…

bash之基本运算符

一.算术运算符 vim test.sh #!/bin/basha10 b20valexpr $a $b echo "a b : $val"valexpr $a - $b echo "a - b : $val"valexpr $a \* $b echo "a * b : $val"valexpr $b / $a echo "b / a : $val"valexpr $b % $a echo "b % a …