【LeetCode】695-岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

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

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：
grid = [
[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：

输入： grid = [[0,0,0,0,0,0,0,0]]
输出： 0

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 为 0 或 1

#广度优先搜索
class Solution(object):
    def maxAreaOfIsland(self, grid):
        n = len(grid)#数列长度
        m = len(grid[0])#数列宽度
        max_S = 0#记录最大面积
        queue = []#队列
        for i in range(n):
            for j in range(m):
                if grid[i][j]==1:#遇见陆地就开始搜索与之相邻的所有陆地
                    S=1
                    grid[i][j]=0
                    queue.append((i,j))
                    while queue:
                        x,y = queue[0]
                        queue.pop(0)
                        for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
                            if 0<=xx<n and 0<=yy<m and grid[xx][yy]==1:
                                S+=1
                                grid[xx][yy]=0
                                queue.append((xx,yy))
                    max_S=max(max_S,S)
        return max_S

class Solution(object):
    def maxAreaOfIsland(self, grid):
        n = len(grid)
        m = len(grid[0])
        max_S = 0
        stack = []
        for i in range(n):
            for j in range(m):
                if grid[i][j]==1:
                    S=1
                    grid[i][j]=0
                    stack.append((i,j))
                    while stack:
                        x,y = stack[-1]
                        stack.pop()
                        for xx,yy in [(x,y+1),(x,y-1),(x+1,y),(x-1,y)]:
                            if 0<=xx<n and 0<=yy<m and grid[xx][yy]==1:
                                S+=1
                                grid[xx][yy]=0
                                stack.append((xx,yy))
                    max_S=max(max_S,S)
        return max_S