深度优先搜索 | 695. 岛屿的最大面积

2024-04-15 14:18

本文主要是介绍深度优先搜索 | 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

二、题解

这道题是一道典型的搜索题,这里的一个岛屿也等价于一个环,所以我们使用深度优先搜索。
深度优先搜索的实现一般需要一个主函数和一个辅助函数,主函数用于遍历所有位置,判断并作为搜索的起点;辅助函数则用于一次的深度优先搜索。其中,深度优先搜索可以用递归或栈来实现,递归实现相对容易,可以用于刷题,栈的话工程里面比较多,可以防止递归栈满的情况。
另外,一旦使用递归的话就要考虑边界条件以及在边界条件下应该进行什么操作。有两种处理递归边界的方法:

  • 先判断边界,再递归
  • 先递归,再判断边界
    这两种方法对应的是辅助函数的两种写法,如下。

注意:在利用递归操作时这里搜索过的位置为了防止再次被搜索,对应的位置要标记为访问过。

三、代码

  • 先判断边界,再递归
class Solution {
public:vector<int> direction{-1,0,1,0,-1};int maxAreaOfIsland(vector<vector<int>>& grid) {if(grid.empty()||grid[0].empty()) return 0;int res = 0;for(int i = 0;i<grid.size();i++){for(int j = 0;j<grid[0].size();j++){if(grid[i][j]== 1){res = max(res,dfs(grid,i,j));}}}return res;}int dfs(vector<vector<int>>& grid,int i,int j){if(grid[i][j]==0) return 0;grid[i][j] = 0;int r,c,count = 1;for(int k=0;k<4;k++){r = i +  direction[k];c =  j+direction[k+1];if(r < grid.size() && c < grid[0].size() && r >=0 && c>=0 && grid[r][c]!=0){count += dfs(grid,r,c);}}return count;}};
  • 先递归,再判断边界
class Solution {
public:vector<int> direction{-1,0,1,0,-1};int maxAreaOfIsland(vector<vector<int>>& grid) {if(grid.empty()||grid[0].empty()) return 0;int res = 0;for(int i = 0;i<grid.size();i++){for(int j = 0;j<grid[0].size();j++){res = max(res,dfs(grid,i,j));}}return res;}int dfs(vector<vector<int>>& grid,int i,int j){if(i < grid.size() && j < grid[0].size() && i >=0 && j>=0 && grid[i][j]!=0){grid[i][j] = 0;return 1+dfs(grid,i-1,j)+dfs(grid,i,j-1)+dfs(grid,i+1,j)+dfs(grid,i,j+1);}else return 0;}};

这篇关于深度优先搜索 | 695. 岛屿的最大面积的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/906046

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操