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

news/2025/2/12 3:22:46/

目录链接:

力扣编程题-解法汇总_分享+记录-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;需要花费几分钟的时间去完成…