当前位置:网站首页>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
边栏推荐
- 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
- "Play with Lighthouse" lightweight application server self built DNS resolution server
- 4.22 study record (you only did water problems in one day, didn't you)
- MySQL —— 16、索引的数据结构
- Introducing vant components on demand
- Design and manufacture of 51 single chip microcomputer solar charging treasure with low voltage alarm (complete code data)
- Install nngraph
- Software testing weekly (issue 68): the best way to solve difficult problems is to wait and see the changes and push the boat with the current.
- Use compressorjs to compress pictures, optimize functions, and compress pictures in all formats
- Free and open source intelligent charging pile SaaS cloud platform of Internet of things
猜你喜欢
内核错误: No rule to make target ‘debian/canonical-certs.pem‘, needed by ‘certs/x509_certificate_list‘
The quill editor image zooms, multiple rich text boxes are used on one page, and the quill editor upload image address is the server address
Use Proteus to simulate STM32 ultrasonic srf04 ranging! Code+Proteus
Summary of JVM knowledge points - continuously updated
Remote access to raspberry pie at home (Part 1)
Hbuilderx + uniapp packaging IPA submission app store stepping on the pit
解决虚拟机中Oracle每次要设置ip的问题
How to click an object to play an animation
HQL find the maximum value in a range
Learning notes of AMBA protocol
随机推荐
How to click an object to play an animation
Utils of various date conversion
AUTOSAR from introduction to mastery 100 lectures (86) - 2F of UDS service foundation
Office 2021 installation package download and activation tutorial
Conflict between Mui picker and drop-down refresh
Async void caused the program to crash
100 lectures on practical application cases of Excel (VIII) - report connection function of Excel
内核错误: No rule to make target ‘debian/canonical-certs.pem‘, needed by ‘certs/x509_certificate_list‘
22. Bracket generation
Async void provoque l'écrasement du programme
GIS practical tips (III) - how to add legend in CASS?
nodeJs + websocket 循环小案例
基于uniapp异步封装接口请求简介
100 GIS practical application cases (51) - a method for calculating the hourly spatial average of NC files according to the specified range in ArcGIS
The El table horizontal scroll bar is fixed at the bottom of the visual window
Golang realizes regular matching: the password contains at least one digit, letter and special character, and the length is 8-16
Brief introduction of asynchronous encapsulation interface request based on uniapp
Teach you to quickly develop a werewolf killing wechat applet (with source code)
安装nngraph
AUTOSAR from introduction to mastery 100 lectures (87) - key weapon of advanced EEA - AUTOSAR and DDS