Leetcode 岛屿最大的面积
题目
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)
示例1:1
2
3
4
5
6
7
8[[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:1
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
思路+代码
一开始想的是动态规划,但是该题没有规律的求解方法,即岛屿的形状无法用统一的方法计算。
此题采用 DFS(深度优先遍历)的方法求解。
DFS一般解体模板(https://blog.csdn.net/weixin_43272781/article/details/82959089)。
1 | int check(参数) |
此题的解法:
边界条件是二维矩阵的边界。
尝试每一种可能是上、下、左、右四个方向进行遍历。
check是是否为陆地(数值是否为1)。
标记是将遍历过的陆地变成海洋(置为0)。
1 | class Solution { |
题目链接:https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1034/