给定一个二维的 0-1 矩阵，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。

Input:

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

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

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

Output: 6

思路：

有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这种做法叫做状态记录或记忆化（memoization）。

一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。当然，我们也可以使用栈（stack）实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时笔者推荐使用递归式写法，同时也方便进行回溯（见下节）。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。我们先展示使用栈的写法：

（1）遍历所有元素

（2）遇到1的直接入栈计算，栈里面所有元素在四个方向有1的继续入栈

（3）标记好已经搜索过的地方

python
def maxAreaOfIsland(grid):
    direction = [-1, 0, 1, 0, -1]
    m = len(grid)  # 行
    n = len(grid[0]) if m else 0  # 列
    area = 0
    for i in range(0, m):
        for j in range(0, n): # （1）遍历所有元素
            if grid[i][j]:  # 首先得确认这是一块陆地，才能往下发展
                local_area = 1
                grid[i][j] = 0
                island = []
                island.append([i, j])
                while len(island): # 遇到1的直接入栈计算，栈里面所有元素在四个方向有1的继续入栈
                    r, c = island.pop()  # 栈顶元素
                    for k in range(0, 4):  # 栈顶元素的四个方向
                        x = r + direction[k]
                        y = c + direction[k + 1]
                        if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == 1:  # 栈顶元素的这个方向遇到的是不是1
                            grid[x][y] = 0
                            local_area += 1
                            island.append([x, y])
                area = max(area, local_area)
    return area
grid_t = [[1, 0, 1, 1, 0, 1, 0, 1],
          [1, 0, 1, 1, 0, 1, 1, 1],
          [0, 0, 0, 0, 0, 0, 0, 1]]
print(maxAreaOfIsland(grid_t))

在辅函数里，一个一定要注意的点是辅函数内递归搜索时，边界条件的判定。边界判定一般

有两种写法，一种是先判定是否越界，只有在合法的情况下才进行下一步搜索（即判断放在调用

递归函数前）；另一种是不管三七二十一先进行下一步搜索，待下一步搜索开始时再判断是否合

法（即判断放在辅函数第一行）。

此外的主函数+辅助函数的写法（C++）:

c
vector<int> direction { -1, 0, 1, 0, -1 };
/* 主函数 */
int maxAreaOfIsland( vector<vector<int> > & grid )
{
 if ( grid.empty() || grid[0].empty() )
  return(0);
 int max_area = 0;
 for ( int i = 0; i < grid.size(); ++i )
 {
  for ( int j = 0; j < grid[0].size(); ++j )
  {
   if ( grid[i][j] == 1 )
   {
    max_area = max( max_area, dfs( grid, i, j ) );
   }
  }
 }
 return(max_area);
}
/* 辅函数 */
int dfs( vector<vector<int> > & grid, int r, int c )
{
 if ( grid[r][c] == 0 )
  return(0);
 grid[r][c] = 0;
 int x, y, area = 1;
 for ( int i = 0; i < 4; ++i )
 {
  x = r + direction[i], y = c + direction[i + 1];
  if ( x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() )
  {
   area += dfs( grid, x, y );
  }
 }
 return(area);
}

c
/* 主函数 */
int maxAreaOfIsland( vector<vector<int> > & grid )
{
 if ( grid.empty() || grid[0].empty() )
  return(0);
 int max_area = 0;
 for ( int i = 0; i < grid.size(); ++i )
 {
  for ( int j = 0; j < grid[0].size(); ++j )
  {
   max_area = max( max_area, dfs( grid, i, j ) );
  }
 }
 return(max_area);
}
/* 辅函数 */
int dfs( vector<vector<int> > & grid, int r, int c )
{
 if ( r < 0 || r >= grid.size() ||
      c < 0 || c >= grid[0].size() || grid[r][c] == 0 )
 {
  return(0);
 }
 grid[r][c] = 0;
 return(1 + dfs( grid, r + 1, c ) + dfs( grid, r - 1, c ) +
        dfs( grid, r, c + 1 ) + dfs( grid, r, c - 1 ) );
}

参考：LeetCode 101：和你一起你轻松刷题（C++）