[leetcode] 1905 statistics sub Island

Here are two for you m x n The binary matrix of grid1 and grid2 , They only contain 0 （ Water area ） and 1 （ Representing land ）. One Islands By Four directions （ Horizontal or vertical ） On the adjacent 1 The composition of the region . Any area outside the matrix is considered a water area .

If grid2 An island of , By grid1 An island of Completely contain , in other words grid2 Every grid in the island is grid1 The same island in the world completely contains , Then we call grid2 This island in China is Sub Islands .

Please return grid2 in Sub Islands Of number .

Example 1：

Input ： grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output ： 3
explain ： As shown in the figure above , On the left for grid1 , On the right is grid2 .
grid2 The winner of the bid is red 1 The area is a sub island , All in all 3 Sub Islands .

Example 2：

** Input ：**grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
** Output ：**2
** explain ：** As shown in the figure above , On the left for grid1 , On the right is grid2 .
grid2 The winner of the bid is red 1 The area is a sub island , All in all 2 Sub Islands .

Tips ：

• m == grid1.length == grid2.length
• n == grid1[i].length == grid2[i].length
• 1 <= m, n <= 500
• grid1[i][j] and grid2[i][j] Either 0 Or 1 .

# Breadth first traversal 
class Solution(object):
    def countSubIslands(self, grid1, grid2):
        m = len(grid2)
        n = len(grid2[0])
        result = 0# Count the number of sub Islands 
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    queue = []
                    grid2[i][j] = 0
                    queue.append((i,j))
                    flag = 1# Whether the flag is a sub Island 
                    while queue:
                        x,y = queue[0]
                        queue.pop(0)
                        if grid1[x][y] == 0:# If in grid1 The corresponding position in is ocean , Then the island is not a sub island 
                            flag = 0
                        for xx,yy in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                            if 0<=xx<m and 0<=yy<n and grid2[xx][yy]==1:
                                grid2[xx][yy] = 0
                                queue.append((xx,yy))
                    result += flag
        return result

# Depth-first traversal 
class Solution(object):
    def countSubIslands(self, grid1, grid2):
        m = len(grid2)
        n = len(grid2[0])
        result = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    stack = []
                    grid2[i][j] = 0
                    stack.append((i,j))
                    flag = 1
                    while stack:
                        x,y = stack[-1]
                        stack.pop()
                        if grid1[x][y] == 0:
                            flag = 0
                        for xx,yy in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:# Traverse in four directions 
                            if 0<=xx<m and 0<=yy<n and grid2[xx][yy]==1:
                                grid2[xx][yy] = 0
                                stack.append((xx,yy))
                    result += flag
        return result