leetcode 695 Max Area of Island

PascalXie 发布于2019-08-15 14:00 / 712人阅读

摘要：返回注意答案并不是因为陆地相连要求必须是在上下左右四个方向。返回应为想法我们还是要遍历数组中的每一个元素。如果数组元素值为，则我们以这个值为起点进行深度优先搜索。

题目详情

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.) 输入一个非空的二维数组，数组由0和1组成。其中0代表水域，1表示陆地。我们需要找出整个数组所表示的地图中，面积最大的一块陆地（陆地的相连只看上下左右相邻的4个元素，如左上方这种就不算相邻！）。
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]]
返回6. 注意答案并不是11, 因为陆地相连要求必须是在上下左右四个方向。
Example 2:
[[0,0,0,0,0,0,0,0]]
返回应为0.

想法

我们还是要遍历数组中的每一个元素。

如果数组元素值为1，则我们以这个值为起点进行深度优先搜索。

遍历当前元素的相邻元素，如果有相邻元素的值为1，那么再以这个元素为起点继续搜索。

为了防止重复，我们每发现一个值为1的元素，就将这个元素赋值为0，代表我们已经遍历过这个元素了。

解法

    int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}}; 
    
    public int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int maxArea = 0;
        int currArea = 0;

        
        for(int row=0;row=0 && newX < grid.length && newY >=0 && newY < grid[0].length){
                if(grid[newX][newY] == 1){
                    grid[newX][newY] = 0;
                    area += findArea(grid,newX,newY);
                    
                }
            }
        }
        
        return area;
    }

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

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

[LeetCode] 695. Max Area of Island

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

dack 2019-08-16 13:43 评论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