​LeetCode解法汇总1254. 统计封闭岛屿的数目

news/2024/4/17 11:51:27

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

二维矩阵 grid 由 0 (土地)和 1 (水)组成。岛是由最大的4个方向连通的 0 组成的群,封闭岛是一个 完全 由1包围(左、上、右、下)的岛。

请返回 封闭岛屿 的数目。

示例 1:

输入:grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出:2
解释:
灰色区域的岛屿是封闭岛屿,因为这座岛屿完全被水域包围(即被 1 区域包围)。

示例 2:

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

示例 3:

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

提示:

  • 1 <= grid.length, grid[0].length <= 100
  • 0 <= grid[i][j] <=1

 

解题思路:

/*** 1254. 统计封闭岛屿的数目* 解题思路:* 标记状态,0代表没有遍历,1代表海域,2代表遍历中,3代表是不是独立岛屿,4代表是独立岛屿。* 然后遍历grid,如果grid[i][j]==0,则查找从这个点触发所有能达到的区域,并记录。返回值是是否是独立岛屿,* 如果是则把所有达到的点改为4,并且数量+1,否则改为3。* 然后继续查找下一个不为0的点。*/

代码:

class Solution {
public:vector<vector<int>> directions = {{1, 0},{0, 1},{-1, 0},{0, -1},};const int STATE_NO_TRAVEL = 0;       // 没有遍历const int STATE_SEA = 1;             // 海域const int STATE_SEARCHING = 2;       // 遍历中const int STATE_NO_CLOSE_ISLAND = 3; // 确定不是独立岛屿const int STATE_CLOSE_ISLAND = 4;    // 确定是独立岛屿bool searchClosedIsland(vector<vector<int>> &grid, bool parentFlag, int x, int y, vector<vector<int>> &record){if (y == 0 || y == grid.size() - 1 || x == 0 || x == grid[0].size() - 1){record.push_back({y, x});return false;}record.push_back({y, x});bool flag = true;for (int i = 0; i < directions.size(); i++){int newX = x + directions[i][1];int newY = y + directions[i][0];// 为3代表正在遍历中if (grid[newY][newX] == STATE_SEARCHING){continue;}// 为1代表遇到海水if (grid[newY][newX] == STATE_SEA){continue;}// 为2代表遇到未封闭的岛屿if (grid[newY][newX] == STATE_NO_CLOSE_ISLAND){flag = false;continue;}// 为0代表未遍历过if (grid[newY][newX] != 0){cout << "error" << endl;}grid[newY][newX] = STATE_SEARCHING;flag = flag & searchClosedIsland(grid, flag, newX, newY, record);}return flag & parentFlag;}int closedIsland(vector<vector<int>> &grid){int sum = 0;vector<vector<int>> record;for (int y = 0; y < grid.size(); y++){for (int x = 0; x < grid[0].size(); x++){if (grid[y][x] != 0){continue;}bool flag = searchClosedIsland(grid, true, x, y, record);if (flag){sum++;}for (auto it : record){// cout << it[0] << " ";grid[it[0]][it[1]] = flag ? STATE_CLOSE_ISLAND : STATE_NO_CLOSE_ISLAND;}record.clear();}}return sum;}
};

 


http://www.ppmy.cn/news/561177.html

相关文章

优化伊通河漂流旅行方案的模型——JLU数学学院2020级数学模型期末大作业

文章目录 题目描述背景介绍模型假设问题一的模型决策树模型游客安全最大化与旅行次数最大化模型统筹考虑游客安全与旅行次数的模型模型对比 第二问的模型每天下水的脚踏游船与电动游船的比率的敏感性分析全是电动游船的情形全是脚踏游船的情形每天下水的脚踏游船与电动游船成比…

c语言小游戏——扫雷

扫雷是一款经典的单人益智游戏&#xff0c;玩家需要在一个由许多方块组成的棋盘上找出所有的地雷&#xff0c;而不触发任何一颗地雷。 int input 0;do{menu();printf("请选择:>");scanf("%d", &input);//输入1进入游戏&#xff0c;输入0退出游戏…

电信设备进网许可证申请需要什么材料?

(一) 电信设备进网许可申请表&#xff08;1份&#xff0c;原件&#xff0c;由工业和信息化部提供格式文本&#xff09;。申请表应当由电信设备进网许可申请人的法定代表人或其委托代理人签字并加盖公章&#xff1b;申请人与生产企业为不同法人的&#xff0c;还应当提供由双方法…

国内首家!华为获5G核心网电信设备进网许可证;亚马逊或颠覆博通等芯片制造商?2020年5G总投资额达0.9万亿元……...

关注并标星星CSDN云计算 速递、最新、绝对有料。这里有企业新动、这里有业界要闻&#xff0c;打起十二分精神&#xff0c;紧跟fashion你可以的&#xff01; 每周两次&#xff0c;打卡即read 更快、更全了解泛云圈精彩news go go go iPhone 12全系渲染图&#xff08;图片来源网…

为什么建议你开一个电子签名钥匙盘?电信设备进网许可证办理

一、哪些业务需要使用电子签名钥匙盘&#xff1f; 电子签名钥匙盘共有4个功能可以使用&#xff0c;分别是“电信设备进网管理系统”申请进网许可、“电信设备进网管理系统”申领进网许可标志、“电信设备识别码登记”国内销售登记、“电信设备识别码登记”出口销售登记。 其…

谈电信级的网络管理

随着目前网络规模和业务的快速发展&#xff0c;网络管理系统的作用越来越重要、也越来越复杂&#xff0c;如何保证网管系统能够724小时对全网进行监控维护&#xff0c;在构建电信级网络的同时如何构建电信级网管&#xff1f;成为一个重要的课题。 一个典型的管理网络主要有如下…

电信 IPRAN 设备组网方案_国内首家5G核心网电信设备进网许可证;电信5G网络增强方案获认可;美国最大规模毫米波拍卖...

点击上方 “通信人才网” 订阅&#xff01; 导读&#xff1a;今日热点 华为荣获国内首家5G核心网电信设备进网许可证 近日&#xff0c; 华为获得工业和信息化部颁发的“5G核心网电信设备进网许可证” 。华为5G核心网支持2G/3G/4G/5G NSA/5G SA全融合&#xff0c;相关网元已按照…

小米和智汀的智能家居设备是通过什么方式进行无线配网的

现如今智能家居的概念已经被广泛家庭接受&#xff0c;许多家庭也将智能家居设备投入到家庭生活中。 每台智能家居设备都是需要完成提前配网的&#xff0c;配网是物联网设备生命周期中最初步骤之一&#xff0c;在你购买新智能家居设备时&#xff0c;需要花费几分钟的时间去完成…

只需五步,中国电信物联网报障指引来了

报障渠道 方式一&#xff1a;人工报障 拨打400-8285656转“0”号键&#xff0c;即可报障 服务时间&#xff1a;7*24小时 方式二&#xff1a;自助报障 搜索“天翼物联”公众号自助报障 服务时间&#xff1a;8:30-20:30 报障五步法 1、准备 发生故障后&#xff0c;先了解故…

小米智能插座监控设备耗电,并自动断电

一.背景: 家人关电视时,经常误操作成熄屏,为了省电,需要统计电视的耗电情况,如果电视不在工作状态或其它条件,则断电 二.购买带用电统计的智能插座: 小米米家智能插座2 蓝牙网关版 APP远程控制 定时开关 过载保护 米家智能插座2 蓝牙网关版 白色【图片 价格 品牌 评论】-京东 三…

中国电信天翼物联品牌升级,注智产业数字化

近期&#xff0c;中国电信天翼物联全面启动了品牌战略升级&#xff0c;通过全新的品牌理念、品牌标志、“CTWing五翼”品牌产品生动阐释了中国电信5G AIoT数字化服务的内涵与行动&#xff0c;“注智”产业数字化和数字产业化。 2021年9月&#xff0c;工信部等八部门印发《物联…

电信运营商基于 MQTT 协议 构建千万级 IoT 设备管理平台

MQTT 是用于物联网的标准消息传递协议。它被设计为一种非常轻量级的发布/订阅消息传送&#xff0c;非常适合以较小的代码占用量和网络带宽连接远程设备。MQTT 协议具有以下特点&#xff1a; 轻巧高效&#xff1a;MQTT 客户端非常小&#xff0c;需要设备资源少。MQTT 消息头很小…

入网许可证_进网许可证、电信设备入网许可证详解!

原标题:进网许可证、电信设备入网许可证详解! 进网许可证也叫入网许可证。入网许可证是加贴在已获得进网许可的电信设备上的质量标志,由信息产业部统一印制和核发,也是行货手机的真品凭证之一。入网许可证上有水印,表面的颜色不均匀,有深有浅,有粗有细;而假的多为复印,…

京东、阿里、小米IoT平台设备接入对比分析

概述 京东、阿里、小米都在积极布局物联网、智能家居方向&#xff0c;经过几年的运营和积累&#xff0c;各家平台接入了不同产品&#xff0c;形成了各自的发展模式。 本报告从平台设备的视角&#xff0c;通过分析各平台设备接入情况&#xff0c;对比已接入的设备品类&#xf…

小米智能家庭网关(一代)配置不成功(4d41)排查情况

问题描述 以下是操作流程&#xff1a; 网关长按5s复位&#xff0c;黄灯正常闪烁&#xff1b; 使用米家app添加网关&#xff0c;如下所示&#xff0c;正常识别到网关设备 按照提示&#xff0c;选择连接的路由器的SSID&#xff0c;并输入正确的密码。 但是到最后一步&#xf…

小米网关+HomeAssistant获取智能硬件数据

因为想获取小米智能网关的温湿度传感器数据的可视化&#xff0c;希望可以和智能网关交互。 最后的技术方案采用&#xff1a;dockerHomeAssistant 1、安装docker 我是在mac上做的&#xff0c;所以去官网下载&#xff0c;一键安装 2、下载HomeAssistant镜像 docker pull hom…

亚商投资顾问早餐FM/0207互联网设备纳入现行进网许可管理

01/亚商投资顾问早间导读 工信部&#xff1a;对卫星互联网设备、功能虚拟化设备纳入现行进网许可管理 质量强国建设纲要印发&#xff1a;到2025年质量整体水平进一步全面提高 河南18部门发文&#xff1a;进一步搞活汽车流通 扩大汽车消费 国资委&#xff1a;加大国防军工等重点…

工业和信息化部发布《关于电信设备进网许可制度若干改革举措的通告》

按照《国务院办公厅关于深化电子电器行业管理制度改革的意见》&#xff08;国办发〔2022〕31号&#xff09;要求&#xff0c;工业和信息化部发布《关于电信设备进网许可制度若干改革举措的通告》&#xff08;工信部信管函〔2023〕14号&#xff09;&#xff0c;集中公布动态调整…

电信设备进网管理

电信送的手机用的很不爽啊&#xff0c;加上电信的终端少&#xff0c;米2的电信版是比较青睐的手机 不知道米2电信版什么时候出&#xff0c;还是看看这个过过瘾好了 电信设备进网管理(http://www.tenaa.com.cn/)

ML算法——线代预备知识随笔【机器学习】

文章目录 数学预备知识3、线性代数3.1、矩阵奇异值分解&#xff08;SVD&#xff09;3.2、广义逆矩阵&#xff08;Moore-Penrose &#xff09;3.3、数据白化&#xff08;Data Whitening&#xff09;3.4、向量导数 4、其它 数学预备知识 3、线性代数 3.1、矩阵奇异值分解&#…
最新文章