695. 岛屿的最大面积

【Description】

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为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。

【Idea】
开始想当然的就以为是动态规划，解了一下发现很多照顾不到的坑。
调试着才意识到想偏了， 其实是个递归/ DFS题。
偏一下： DFS即不撞南墙不回头，一般解法就是递归，遍历到无解就回头。
def DFS():
if 找到解 | 走到头 无需再往下走：
return 0
elif 还可继续走:
分情况调用self.DFS()
（循环递归时记得更新访问数组，避免重复访问导致计算错误或者复杂度过高
常借助两个tmp数组：
一个用于访问标记来减少重复检索；
另一个栈类型，先进后出，用于暂存需要遍历的元素。此题由于一个元素坐标只往四面走，所以直接写出来就OK，可以不用栈暂存。

【Solution】

class Solution:
    def dfs(self, arr, x, y):
        if x<0 or y<0 or x>=len(arr) or y>=len(arr[0]) or arr[x][y]==0:
            return 0    # 到头
        arr[x][y] = 0   # 访问标记
        return 1+self.dfs(arr, x+1, y)+self.dfs(arr, x-1, y) +self.dfs(arr, x, y+1)+self.dfs(arr, x, y-1) # 四个方向，这里按题意不同，也可改为栈的行为缓存需要访问的坐标list

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                ans = max(self.dfs(grid, i, j), ans)
        return ans