0695. Max Area of Island

---

You are given an m x n binary matrix grid.

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.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: 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]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [0,0,0,0,0,0,0,0](/kumaeki/LeetCode/wiki/0,0,0,0,0,0,0,0)
Output: 0

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

---

解法1

用另一个一样大的数组来记录是否访问过这个节点. 然后遍历每一个点就好了.

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] memo = new boolean[m][n];
        int res = 0; 
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                res = Math.max(res, helper(grid, memo, i, j));
        return res; 
    }
    
    private int helper(int[][] grid, boolean[][] memo, int i, int j){
        if(i < 0 || i == grid.length || j < 0 || j == grid[0].length || memo[i][j] || grid[i][j] == 0)
            return 0;
        memo[i][j] = true;
        return 1 + helper(grid, memo, i - 1, j) + helper(grid, memo, i + 1, j) + helper(grid, memo, i, j - 1) + helper(grid, memo, i, j + 1);
    } 
}

---

解法2

不另外建立一个二维数组, 而是更改grid本身的值. 在所有处理结束之后再把值恢复.

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int res = 0; 
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                res = Math.max(res, helper(grid, i, j));
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                grid[i][j] = -grid[i][j];
        
        return res; 
    }
    
    private int helper(int[][] grid, int i, int j){
        if(i < 0 || i == grid.length || j < 0 || j == grid[0].length || grid[i][j] != 1)
            return 0;
        grid[i][j] = -1;
        return 1 + helper(grid,  i - 1, j) + helper(grid, i + 1, j) + helper(grid, i, j - 1) + helper(grid, i, j + 1);
    }

}