[leetcode] 695 - maximum area of the island

Give you a size of m x n The binary matrix of grid .

Islands It's made up of some neighboring 1 ( Representing land ) A combination of components , there 「 adjacent 」 Ask for two 1 Must be in In four horizontal or vertical directions adjacent . You can assume grid The four edges of are all 0（ Representative water ） Surrounded by a .

The area of the island is the value of 1 Number of cells .

Calculate and return grid The largest island area in . If there were no Islands , Then the return area is 0 .

Example 1：

Input ：
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]]
Output ： 6
explain ： The answer should not be 11 , Because the island can only contain horizontal or vertical 1 .

Example 2：

Input ： grid = [[0,0,0,0,0,0,0,0]]
Output ： 0

Tips ：

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

# Breadth first search 
class Solution(object):
    def maxAreaOfIsland(self, grid):
        n = len(grid)# Sequence length 
        m = len(grid[0])# Sequence width 
        max_S = 0# Record the maximum area 
        queue = []# queue 
        for i in range(n):
            for j in range(m):
                if grid[i][j]==1:# When you meet land, you start to search all the land adjacent to it 
                    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