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.

應(yīng)該說(shuō)是基礎(chǔ)的DFS題絮缅，但是巨久沒(méi)有寫(xiě)搜索了，感覺(jué)完全不會(huì)BFS和DFS了现诀。做完了contest第二天看了下答案做瞪，發(fā)現(xiàn)跟Number of islands這種題完全就是一樣的套路舌缤，感覺(jué)最近必須得回歸基礎(chǔ)了旱爆。別去搞什么太fancy的東西踪宠，講真那些高大上的項(xiàng)目寫(xiě)在簡(jiǎn)歷上步势，真有那個(gè)水平早就在工業(yè)界拿高薪了氧猬，怎么可能還在找實(shí)習(xí)』荡瘢回歸算法和數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)盅抚，做好基礎(chǔ)題，熟悉基礎(chǔ)套路倔矾，我覺(jué)得完全夠了妄均。

這道題用的是DFS, 具體為灌水法。我們用兩個(gè)for循環(huán)搜索grid, 每次遇到0就continue; 遇到1就進(jìn)行DFS, 然后更新當(dāng)前的maxArea. DFS返回的是當(dāng)前grid[i][j]所在島嶼的最大面積哪自。我們先判斷該點(diǎn)是否在規(guī)定范圍內(nèi)丰包，然后將grid[i][j] == 1的點(diǎn)先標(biāo)為0，就好像是吃掉了這個(gè)島壤巷。同時(shí)邑彪，我們也要對(duì)這個(gè)點(diǎn)周?chē)膫€(gè)方向的點(diǎn)進(jìn)行DFS搜索，將所有鏈接起來(lái)的島標(biāo)為0隙笆，形象地比喻就好像灌水一樣锌蓄，一口吃掉所有連接的島。我們返回的時(shí)候撑柔，要返回上下左右所有DFS的值之和加上1. 如果grid[i][j] == 0,則DFS method直接返回0.

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