Leetcode 695. Max Area of Island

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.)

思路：

1. 我们可以遍历每个岛，找出那个最大面积的岛。
2. 遍历2维数组中每一个元素，如果它是1，则沿着它继续向周围搜索，找到所有毗邻的陆地，这样最终可以得到它所在的那个岛的面积。
3. 每遍历到一个陆地，需要把它标记为0，否则搜索它毗邻陆地的时候，会重复的搜索回来。
4. 用一个最大值变量来存储当前遍历到的最大面积。

public class MaxAreaIsland695 {
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid[0].length == 0 || grid[0].length == 0) {
            return 0;
        }

        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    maxArea = Math.max(maxArea, searchArea(grid, i, j));
                }
            }
        }

        return maxArea;
    }

    private int searchArea(int[][] grid, int x, int y) {
        grid[x][y] = 0;
        int curArea = 1;
        for (int d = 0; d < 4; d++) {
            int tx = x + dx[d];
            int ty = y + dy[d];
            if (tx < 0 || tx >= grid.length || ty < 0 || ty >= grid[0].length || grid[tx][ty] == 0) {
                continue;
            }

            curArea += searchArea(grid, tx, ty);
        }

        return curArea;
    }
}