[LeetCode] 695. Max Area of Island

dack 发布于2019-08-16 13:43 / 2213人阅读

Problem

Given a non-empty 2D array grid of 0"s and 1"s, an island is a group of 1"s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[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]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

Solution

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        if (grid == null || grid.length == 0 || grid[0].length == 0) return max;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) max = Math.max(max, dfs(grid, i, j));
            }
        }
        return max;
    }
    
    private int dfs(int[][] grid, int i, int j) {
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1) {
            grid[i][j] = 0;
            return 1+dfs(grid, i-1, j)+dfs(grid, i+1, j)+dfs(grid, i, j-1)+dfs(grid, i, j+1);
        }
        return 0;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72223.html

leetcode 695 Max Area of Island

摘要：返回注意答案并不是因为陆地相连要求必须是在上下左右四个方向。返回应为想法我们还是要遍历数组中的每一个元素。如果数组元素值为，则我们以这个值为起点进行深度优先搜索。题目详情 Given a non-empty 2D array grid of 0s and 1s, an island is a group of 1s (representing land) connected 4-di...

PascalXie 2019-08-15 14:00 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
LeetCode 695. 岛屿的最大面积【c++/java详细题解】

摘要：找到给定的二维数组中最大的岛屿面积。思路给定一个由和组成的二维数组，其中代表岛屿土地，要求找出二维数组中最大的岛屿面积，没有则返回。样例如样例所示，二维数组的最大岛屿面积为，下面来讲解深度优先搜索的做法。 ...

MangoGoing 2021-09-04 16:41 评论0 收藏0
[LeetCode] Island Perimeter

Problem You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is com...

robin 2019-08-19 11:09 评论0 收藏0
leetcode463. Island Perimeter

摘要：要求计算出岛屿的周长。思路和代码这题不难，直观的来看，其实只要判断出这一块土地几面临海就知道需要加上几条边长。临海的判断有两个，一个是这块地位于数组的边缘，一个是这块地相邻的元素为，即海洋。代码如下上方临海左侧临海右侧临海下方临海题目要求 You are given a map in form of a two-dimensional integer grid where 1 rep...

Raaabbit 2019-08-19 10:25 评论0 收藏0