leetcode 695 Max Area of Island

PascalXie 發(fā)布于2019-08-15 14:00 / 714人閱讀

摘要：返回注意答案并不是因為陸地相連要求必須是在上下左右四個方向。返回應(yīng)為想法我們還是要遍歷數(shù)組中的每一個元素。如果數(shù)組元素值為，則我們以這個值為起點進(jìn)行深度優(yōu)先搜索。

題目詳情

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.) 輸入一個非空的二維數(shù)組，數(shù)組由0和1組成。其中0代表水域，1表示陸地。我們需要找出整個數(shù)組所表示的地圖中，面積最大的一塊陸地（陸地的相連只看上下左右相鄰的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]]
返回應(yīng)為0.

想法

我們還是要遍歷數(shù)組中的每一個元素。

如果數(shù)組元素值為1，則我們以這個值為起點進(jìn)行深度優(yōu)先搜索。

遍歷當(dāng)前元素的相鄰元素，如果有相鄰元素的值為1，那么再以這個元素為起點繼續(xù)搜索。

為了防止重復(fù)，我們每發(fā)現(xiàn)一個值為1的元素，就將這個元素賦值為0，代表我們已經(jīng)遍歷過這個元素了。

解法

    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;
    }