图论基础|695. 岛屿的最大面积、1020. 飞地的数量、130. 被围绕的区域

695. 岛屿的最大面积

力扣题目链接(opens new window)

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

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

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

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

  • 输入: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 。

思路:广度优先和深度优先皆可,遍历的时候计数,然后取最大数量即可

class Solution {
public://深度优先版本int count=0;int result =0;int dir[4][2]={0,1,1,0,-1,0,0,-1};void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){for(int i=0;i<4;i++){int nextx= x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){visited[nextx][nexty]=true;count++;dfs(grid,visited,nextx,nexty);}}}int maxAreaOfIsland(vector<vector<int>>& grid) {int n=grid.size(); int m=grid[0].size();vector<vector<bool>>visited=vector<vector<bool>>(n,vector<bool>(m,false));for(int i=0;i<n;i++){for(int j=0; j<m;j++){if(!visited[i][j]&&grid[i][j]==1){count=1;//遇到陆地先计数visited[i][j]=true;dfs(grid,visited,i,j);result=max(result,count);}}}return result;}
};
//广度优先版本
class Solution {
public:int count=0;int result =0;int dir[4][2]={0,1,1,0,-1,0,0,-1};void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){queue<int>que;que.push(x);que.push(y);visited[x][y]=true;count++;while(!que.empty()){int xx=que.front(); que.pop();int yy=que.front(); que.pop();for(int i=0;i<4;i++){int nextx=  xx+dir[i][0];int nexty=  yy+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){visited[nextx][nexty]=true;count++;que.push(nextx);que.push(nexty);}}}}int maxAreaOfIsland(vector<vector<int>>& grid) {int n=grid.size(); int m=grid[0].size();vector<vector<bool>>visited=vector<vector<bool>>(n,vector<bool>(m,false));for(int i=0;i<n;i++){for(int j=0; j<m;j++){if(!visited[i][j]&&grid[i][j]==1){count=0;visited[i][j]=true;dfs(grid,visited,i,j);result=max(result,count);}}}return result;}
};

1020. 飞地的数量

力扣链接(opens new window)

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

  • 输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
  • 输出:3
  • 解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。

  • 输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
  • 输出:0
  • 解释:所有 1 都在边界上或可以到达边界

思路:本题要求找到不靠边的陆地面积,那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋,然后再去重新遍历地图的时候,统计此时还剩下的陆地就可以了。

遍历周边:分别遍历最左列(grid[i][0]),最右列(grid[i][m-1]),最上行(grid[0][j]),最下行(grid[n-1][j]),同时进行搜索,在搜索过程中将其置0。

class Solution {
public://深度优先搜索int dir[4][2]={1,0,0,1,-1,0,0,-1};//四个方向int count;void dfs(vector<vector<int>>& grid, int x, int y){grid[x][y]=0;count++;for(int i=0; i<4; i++){int nextx= x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(grid[nextx][nexty]==1){// count++;// grid[nextx][nexty]=0;dfs(grid, nextx, nexty);}}return;}int numEnclaves(vector<vector<int>>& grid) {// int count=0;int n=grid.size();//行数int m=grid[0].size();//列数//遍历周边for(int i=0;i<n;i++){if(grid[i][0])dfs(grid, i,0);//遍历最左列if(grid[i][m-1])dfs(grid,i, m-1);//遍历最右列}for(int j=0; j<m;j++){if(grid[0][j])dfs(grid, 0, j);//遍历最上行if(grid[n-1][j])dfs(grid,n-1, j);//遍历最底行}//遍历整个网格,并计数count= 0;for(int i=0; i<n; i++){for(int j=0; j<m;j++){if(grid[i][j]){// count++;dfs(grid,i, j);}}}return count;}
};
//广度优先搜索
class Solution {
public:int count =0;int dir[4][2]={0,1,1,0,0,-1,-1,0};void bfs(vector<vector<int>>& grid, int x, int y){queue<pair<int,int>>que;que.push({x,y});count++;grid[x][y]=0;while(!que.empty()){pair<int,int>cur=que.front();que.pop();for(int i=0;i<4;i++){int nextx=cur.first+dir[i][0];int nexty=cur.second+dir[i][1];if(nextx<0||nextx>=grid.size()||nexty<0||nexty>=grid[0].size())continue;if(grid[nextx][nexty]){que.push({nextx,nexty});count++;grid[nextx][nexty]=0;}}}return;}int numEnclaves(vector<vector<int>>& grid) {int n=grid.size();//行数int m=grid[0].size();//列数//遍历周边并置0for(int i=0;i<n;i++){if(grid[i][0])bfs(grid,i,0);//遍历最左列if(grid[i][m-1])bfs(grid,i,m-1);//遍历最右列}for(int j=0;j<m;j++){if(grid[0][j]) bfs(grid,0,j);//遍历第一行if(grid[n-1][j]) bfs(grid,n-1,j);//遍历最后一行}//重新遍历整个网格并计算count=0;for(int i=0; i<n;i++) {for(int j=0;j<m;j++){if(grid[i][j]){bfs(grid,i,j);}}}return count;}
};

130. 被围绕的区域

题目链接(opens new window)

给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

  • 输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
  • 输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
  • 解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的

思路:和上一题类似,只是需要把’飞地‘改为”X"

先广度优先或深度优先遍历周边,把周边的X换为'A',然后两个for循环遍历整个grid,遇到'A'换成’O',遇到'O'换成‘X'

//广度优先搜索
class Solution {
public:int dir[4][2]={0,1,1,0,0,-1,-1,0};void dfs(vector<vector<char>>& board, int x, int y){board[x][y]='A';for(int i=0;i<4;i++){int nextx=x+dir[i][0];int nexty=y+dir[i][1];if(nextx<0||nextx>=board.size()||nexty<0||nexty>=board[0].size())continue;if(board[nextx][nexty]=='O'){dfs(board,nextx,nexty);}}return;}void solve(vector<vector<char>>& board) {int n=board.size();//行数int m=board[0].size();//列数//遍历周边,把周边的'O'换成’A‘for(int i=0;i<n;i++){if(board[i][0]=='O')dfs(board,i,0);//遍历最左列if(board[i][m-1]=='O')dfs(board,i,m-1);//遍历最右列}for(int j=0;j<m;j++){if(board[0][j]=='O')dfs(board,0,j);//最上行if(board[n-1][j]=='O')dfs(board,n-1,j);//最下行}//遍历整个网格并替换for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(board[i][j]=='O')board[i][j]='X';if(board[i][j]=='A') board[i][j]='O';}}}
};
class Solution {
public:int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};void bfs(vector<vector<char>>& board, int x, int y) {queue<pair<int, int>> que;que.push({x, y});board[x][y]='A';while (!que.empty()) {pair<int, int> cur = que.front();que.pop();for (int i = 0; i < 4; i++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if (nextx < 0 || nextx >= board.size() || nexty < 0 ||nexty >= board[0].size())continue;if (board[nextx][nexty] == 'O') {board[nextx][nexty] = 'A';// cout<<"board[nextx][nexty]:"<<board[nextx][nexty]<<endl;que.push({nextx, nexty});}}}}void solve(vector<vector<char>>& board) {int n = board.size();int m = board[0].size();// 遍历周边for (int i = 0; i < n; i++) {if (board[i][0] == 'O')bfs(board, i, 0);if (board[i][m - 1] == 'O')bfs(board, i, m - 1);}for (int j = 0; j < m; j++) {if (board[0][j] == 'O')bfs(board, 0, j);if (board[n - 1][j] == 'O')bfs(board, n - 1, j);}// 遍历整个网格并替换for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// cout<<"before: "<<board[i][j]<<endl;if (board[i][j] == 'O')board[i][j] = 'X';if (board[i][j] == 'A')board[i][j] = 'O';}}}
};

 参考:代码随想录

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

何为布控球?布控球的分类对比

主要的分类有&#xff1a; 根据内部的主控板卡的系统分类&#xff0c;典型的是基于海思芯片的嵌入式LINUX系统的&#xff0c;一般出国标GB28181&#xff0c;另外一种是剑走偏锋的安卓系统的&#xff0c;需要把球机的输出YUV转换为UVC接入安卓主板&#xff0c;作为外接USB摄像头…

FreeRTOS从代码层面进行原理分析(1 任务的建立)

FreeRTOS_分析 FreeRTOS 是一个开源的实时操作系统。可以在很的低内存使用的情况下运行在单片机上&#xff0c;使得单片机可以并发(虽然某一时刻还是只有一个任务运行) 的运行程序。关于一些 FreeRTOS 优缺点的介绍文章很多&#xff0c;这里就不再赘述直接深入代码探究原理。 …

vscode用SSH远程开发c语言

vscode配置远程 这里我使用虚拟机进行展示&#xff0c;首先需要你的虚拟机安装好ssh 没安装好就执行下面的命令安装并开启服务 sudo apt-get install ssh sudo service ssh start ps -e | grep sshvscode安装 remote-ssh扩展 点击左下角的远程连接&#xff0c;我这里已经连接…

mysql 存储引擎 基本介绍

目录 一 存储引擎概念介绍 &#xff08;一&#xff09;存储引擎概念 &#xff08;二&#xff09;MySQL常用的存储引擎 &#xff08;三&#xff09;存储引擎运作方式 二 MyISAM 存储引擎介绍 &#xff08;一&#xff09; MyISAM 存储引擎特点 1&#xff0c;不支持…

8.测试教程-自动化测试selenium-3

文章目录 1.unittest框架解析2.批量执行脚本2.1构建测试套件2.2用例的执行顺序2.3忽略用例执行 3.unittest断言4.HTML报告生成5.异常捕捉与错误截图6.数据驱动 大家好&#xff0c;我是晓星航。今天为大家带来的是 自动化测试selenium第三节 相关的讲解&#xff01;&#x1f600…

四、Elasticsearch 进阶

自定义目录 4.1 核心概念4.1.1 索引&#xff08;Index&#xff09;4.1.2 类型&#xff08;Type&#xff09;4.1.3 文档&#xff08;Document&#xff09;4.1.3 字段&#xff08;Field&#xff09;4.1.5 映射&#xff08;Mapping&#xff09;4.1.6 分片&#xff08;Shards&#…

可视化技术干货:坐标系扫盲—图表呈现的核心,有点难懂,慢慢看

hello&#xff0c;我是贝格前端工场&#xff0c;本篇文章开始分享可视化干货技术&#xff0c;力争用深入浅出的语言讲明白坐标系&#xff0c;并附大量图表案例。欢迎老铁们关注转发&#xff0c;如有项目定制需求可以私信我们。 一、什么是坐标系 在可视化设计中&#xff0c;坐…

【Linux】进程地址空间详解

前言 在我们学习C语言或者C时肯定都听过老师讲过地址的概念而且老师肯定还会讲栈区、堆区等区域的概念&#xff0c;那么这个地址是指的物理内存地址吗&#xff1f;这里这些区域又是如何划分的呢&#xff1f; 我们在使用C语言的malloc或者C的new函数开辟空间时&#xff0c;开辟…

Spring Cloud三:API网关深入探索与实战应用

Spring Cloud一&#xff1a;Spring Cloud 简介 Spring Cloud二&#xff1a;核心组件解析 一、服务发现与动态路由 在微服务架构中&#xff0c;服务的动态注册与发现是一个核心功能。API网关可以与服务注册中心&#xff08;如Eureka、Consul等&#xff09;集成&#xff0c;动态…

C# 将 Word 转文本存储到数据库并进行管理

目录 功能需求 范例运行环境 设计数据表 关键代码 组件库引入 Word文件内容转文本 上传及保存举例 得到文件Byte[]数据方法 查询并下载Word文件 总结 功能需求 将 WORD 文件的二进制信息存储到数据库里&#xff0c;即方便了统一管理文件&#xff0c;又可以实行权限控…

安装IK分词器 + 扩展词典配置 + 停用词典配置

安装IK分词器 1.在线安装ik插件&#xff08;较慢&#xff09; # 进入容器内部 docker exec -it elasticsearch /bin/bash ​ # 在线下载并安装 ./bin/elasticsearch-plugin install https://github.com/medcl/elasticsearch-analysis-ik/releases/download/v7.12.1/elastics…

算法---动态规划

动态规划 1.前言2. 示例 - 第N个泰波那契数2.1 算法原理&#xff08;重点&#xff09;2.2 代码 3. 总结解题思路 1.前言 哪些情况下会用到动态规划&#xff1a; 1.最优化问题&#xff1a;当需要求解最大值或最小值的问题时&#xff0c;可以考虑使用动态规划。例如&#xff0c…

[C语言]——内存函数

目录 一.memcpy使用和模拟实现&#xff08;内存拷贝&#xff09; 二.memmove 使用和模拟实现 三.memset 函数的使用&#xff08;内存设置&#xff09; 四.memcmp 函数的使用 C语言中规定&#xff1a; memcpy拷贝的就是不重叠的内存memmove拷贝的就是重叠的内存但是在VS202…

SecureCRT:高效安全的远程连接工具

SecureCRT是一款功能强大的终端仿真工具&#xff0c;主要用于连接和运行包括Windows、UNIX和VMS在内的远程系统。它支持多种协议&#xff0c;如SSH1、SSH2、Telnet、SFTP、Rlogin、Serial、SCP等&#xff0c;确保用户与目标设备之间的通信安全&#xff0c;并防止网络攻击和窥探…

Android Preference简单介绍

Android Preference简单介绍 文章目录 Android Preference简单介绍一、前言二、Preference 简单介绍二、PreferenceScreen和SwitchPreference 简单示例2、相关demo代码示例&#xff08;1&#xff09;SettingsActivity.Java&#xff08;2&#xff09;layout\settings_activity.x…

局域网内的手机、平板、电脑的文件共享

在日常工作生活中&#xff0c;经常需要将文件在手机、平板、电脑间传输&#xff0c;以下介绍三种较为便捷的方法&#xff1a; 1.LocalSend 该软件是免费开源的&#xff0c;可以在局域网内的任意手机、平板、电脑间传递文件&#xff0c;并且任意一方都可以作为“发送方”和“接…

taro框架之taro-ui中AtSwipeAction的使用

题记&#xff1a;所需效果&#xff1a;滑动删除 工作进程 官网文档代码 <AtSwipeAction options{[{text: 取消,style: {backgroundColor: #6190E8}},{text: 确认,style: {backgroundColor: #FF4949}} ]}><View classNamenormal>AtSwipeAction 一般使用场景</…

DataEase大屏iframe嵌入自建网站(React)

1、修改dataease 所在的服务器nginx配置 server {listen 80;server_name dataease.ibaiqiu.cn;return 307 https://$host$request_uri; } server {listen 443 ssl;server_name dataease.ibaiqiu.cn;client_max_body_size 30M;ssl_certificate /usr/local/nginx/co…

计算机三级——网络技术(综合题第二题)

路由器工作模式 用户模式 当通过Console或Telnet方式登录到路由器时&#xff0c;只要输入的密码正确&#xff0c;路由器就直接进入了用户模式。在该模式下&#xff0c;系统提示符为一个尖括号(>)。如果用户以前为路由器输入过名称&#xff0c;则该名称将会显示在尖指号的前…

HarmonyOS应用开发实战 - Api9 拍照、拍视频、选择图片、选择视频、选择文件工具类

鸿蒙开发过程中&#xff0c;经常会进行系统调用&#xff0c;拍照、拍视频、选择图库图片、选择图库视频、选择文件。今天就给大家分享一个工具类。 1.话不多说&#xff0c;先展示样式 2.设计思路 根据官方提供的指南开发工具类&#xff0c;基础的拍照、拍视频、图库选照片、选…