当前位置:网站首页>LeetCode_DFS_中等_695.岛屿的最大面积
LeetCode_DFS_中等_695.岛屿的最大面积
2022-04-23 13:07:00 【一瓢江湖我沉浮】
目录
1.题目
给你一个大小为 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)
链接:https://leetcode-cn.com/problems/max-area-of-island
2.思路
(1)DFS
本题实际上是LeetCode_DFS_中等_200.岛屿数量这题的变形,只不过 dfs 函数淹没岛屿的同时,要记录这个岛屿的面积。
3.代码实现(Java)
//思路1————DFS
class Solution {
public int maxAreaOfIsland(int[][] grid) {
//res记录岛屿的最大面积,初始值为0
int res = 0;
int m = grid.length;
int n = grid[0].length;
//遍历grid
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
//淹没该岛屿,并且更新res
res = Math.max(res, dfs(grid, i, j));
}
}
}
return res;
}
//淹没与(i, j)相邻的陆地,并且返回被淹没的陆地面积
public int dfs(int[][] grid, int i, int j) {
int m = grid.length;
int n = grid[0].length;
//检查边界条件
if (i < 0 || j < 0 || i >= m || j >= n) {
return 0;
}
if (grid[i][j] == 0) {
//该位置是海水,直接返回
return 0;
}
//将(i, j)变成海水
grid[i][j] = 0;
return dfs(grid, i - 1, j) +
dfs(grid, i + 1, j) +
dfs(grid, i, j - 1) +
dfs(grid, i, j + 1) + 1;
}
}
版权声明
本文为[一瓢江湖我沉浮]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_43004044/article/details/124359093
边栏推荐
- Design and manufacture of 51 single chip microcomputer solar charging treasure with low voltage alarm (complete code data)
- Introducing vant components on demand
- 8086 of x86 architecture
- 100 GIS practical application cases (34) - splicing 2020globeland30
- Wonderful review | the sixth issue of "source" - open source economy and industrial investment
- About the 'enum' enumeration type and structure.
- Learning materials
- AUTOSAR from introduction to mastery 100 lectures (81) - FIM of AUTOSAR Foundation
- Go language array operation
- Summary of JVM knowledge points - continuously updated
猜你喜欢
Synchronously update the newly added and edited data to the list
The filter() traverses the array, which is extremely friendly
AUTOSAR from introduction to mastery 100 lectures (86) - 2F of UDS service foundation
PC starts multiple wechat at one time
nodejs + mysql 实现简单注册功能(小demo)
将新增和编辑的数据同步更新到列表
Design of body fat detection system based on 51 single chip microcomputer (51 + OLED + hx711 + US100)
melt reshape decast 长数据短数据 长短转化 数据清洗 行列转化
filter()遍历Array异常友好
mui + hbuilder + h5api模拟弹出支付样式
随机推荐
4.22 study record (you only did water problems in one day, didn't you)
Read the data in Presto through sparksql and save it to Clickhouse
How to click an object to play an animation
mui picker和下拉刷新冲突问题
mysql8安装
The filter() traverses the array, which is extremely friendly
Importerror after tensorflow installation: DLL load failed: the specified module cannot be found, and the domestic installation is slow
mui + hbuilder + h5api模拟弹出支付样式
将新增和编辑的数据同步更新到列表
The project file '' has been renamed or is no longer in the solution, and the source control provider associated with the solution could not be found - two engineering problems
Hbuilderx + uniapp packaging IPA submission app store stepping on the pit
Custom nail robot alarm
mui 微信支付 排坑
Connect orcale
31. 下一个排列
These vscode extensions are my favorite
Packet capturing and sorting -- TCP protocol [8]
Important knowledge of network layer (interview, reexamination, term end)
51 single chip microcomputer stepping motor control system based on LabVIEW upper computer (upper computer code + lower computer source code + ad schematic + 51 complete development environment)
STM32 is connected to the motor drive, the DuPont line supplies power, and then the back burning problem