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

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

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

示例 1：

  1. [[0,0,1,0,0,0,0,1,0,0,0,0,0],
  2.  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  3.  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  4.  [0,1,0,0,1,1,0,0,1,0,1,0,0],
  5.  [0,1,0,0,1,1,0,0,1,1,1,0,0],
  6.  [0,0,0,0,0,0,0,0,0,0,1,0,0],
  7.  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  8.  [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2：

  1. [[0,0,0,0,0,0,0,0]]

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

提示：

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

思路

想象我们拿个颜料桶，从(0, 0) 的位置开始遍历整个图，当遇到小岛'1'时，我们就给把颜料涂在地上；当遇到水'0'时，我们就不涂颜色。

我们需要维护一个int color[][]数组，里面的值表示不同的颜色（也表示不同的小岛）。我们遍历完整个图，再数一数我们用了几种颜色就求出小岛的数量了。在DFS中，如果该岛屿没有涂过颜色，就把当前面积cur_area自增。离开DFS后，和当前最大面积做对比，重新选择面积最大的那个。

DFS到什么时候停止呢？当我们走到一个涂过颜色的方格，我们就停止继续深度优先搜索。

DFS如何遍历周围的节点？我们按照题目要求判断垂直方向，水平方向没有越界，然后上下左右四个方向分别来一次DFS就行了。

代码

  1. class Solution {
  2. public:
  3.     int id_island = 0;
  4.     int cur_area = 0;
  5.     int MAX_AREA = 0;
  7.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  8.         if( grid.size() == 0 )      return 0;
  9.         if( grid[0].size() == 0 )   return 0;
  11.         int color[ grid.size() ][ 50 ];
  12.         memset( color, 0x0, sizeof(color) );
  14.         // Walk every node in grid
  15.         for(int i = 0; i < grid.size(); i++) {
  16.             for(int j = 0; j < grid[0].size(); j++) {
  17.                 if( color[i][j] == 0 && grid[i][j] == 1 ) {
  18.                     (this->id_island) ++;
  19.                     this->cur_area = 0;
  20.                     dfs(grid, color, i, j);
  21.                     this->MAX_AREA = this->cur_area > this->MAX_AREA ? this->cur_area : this->MAX_AREA;
  22.                 }
  23.             }
  24.         }
  26.         return this->MAX_AREA;
  27.     }
  29.     void dfs(vector<vector<int>>& grid, int color[][50], int row, int col) {
  30.         // 1. Exit condition
  31.         if( color[row][col] )   return;
  33.         // 2. Walk every island that not colored
  34.         if( grid[row][col] == 1 ) {
  35.             (this->cur_area) ++;;
  36.             color[row][col] = this->id_island;
  37.             if( row-1 >= 0 )                dfs(grid, color, row-1, col);  // Up
  38.             if( row+1 < grid.size() )       dfs(grid, color, row+1, col);  // Down
  39.             if( col-1 >= 0 )                dfs(grid, color, row, col-1);  // Left
  40.             if( col+1 < grid[0].size() )    dfs(grid, color, row, col+1);  // Right
  41.         }       
  42.     }
  43. };