问题描述：

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 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 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

深搜很简单。
grid自身充当visited数组

class Solution {
public:
    int step[4][2] ={{0,1},{0,-1},{1,0},{-1,0}};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if((grid.size()==0)||(grid[0].size()==0))
        return 0;
        int res = 0;
        for(int i = 0; i <grid.size();++i){
            for(int j = 0; j < grid[i].size(); ++j){
                if(grid[i][j])
                res = max(dfs(grid,i,j),res);
            }
        }
        return res;
    }
    int dfs(vector<vector<int>> & grid,int i, int j){
        if((i < 0)||(i >= grid.size())||(j < 0)||(j >= grid[i].size()))
        return 0;
        if(grid[i][j] == 0) return 0;
        int area = 1;
        grid[i][j] = 0;
        for(int k = 0; k < 4; ++k){
            area+=dfs(grid,i+step[k][0],j + step[k][1]);
        }
        return area;
    }
};

但是我好想用dp啊~但是还用不明白。
又尝试着用dp来解，emmm就卡死了，应该不能用dp吧

  • dp很难解决同一块区域发生分叉的情况。
  • dfs的时间复杂度是O(N)，没办法再降低了

下面的解法是错误的。

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if((grid.size()==0)||(grid[0].size()==0)) return 0;
        return countRow(grid);
    }


    int countRow(vector<vector<int>> & grid){
        int res = 0;
       for(int i = 0; i < grid.size(); ++i){
            for(int j = 1; j < grid[0].size(); ++j){
                if(grid[i][j] == 0) continue;
                grid[i][j] += grid[i][j-1];//横向累加
                if(grid[i][j] > res) res = grid[i][j];
                if((j == (grid[0].size()-1))||(grid[i][j+1] == 0)){//到达横向终点，开始反溯
                    if((i + 1 < grid.size())&&(grid[i+1][j])){
                        grid[i+1][j] += grid[i][j];
                    }
                    int k = j;
                    while((k > 0)&&(grid[i][k-1] != 0)){
                        grid[i][k-1] = grid[i][k];
                        --k;
                        if(isEgde(grid,i+1,k)){
                            grid[i+1][k] += grid[i][k];
                        }
                    }
                }

            }
        }
        return res;

    }
    bool isEgde(vector<vector<int>>& grid, int i, int j){//最右方
        if((i < 0)||(i >= grid.size())||( j < 0)||(j >= grid[0].size()))
        return false;
        if(!grid[i][j]) return false;
        return (j == (grid[0].size()-1))||(!grid[i][j+1]);
    }
};