[leetcode] 1020 number of enclaves

Give you a size of m x n The binary matrix of grid , among 0 Represents an ocean cell 、1 Represents a land cell .

once Move It refers to walking from one land cell to another （ On 、 Next 、 Left 、 Right ） Land cells or across grid The boundary of the .

Return to grid unable The number of land cells that leave the grid boundary in any number of moves .

Example 1：

Input ： grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output ： 3
explain ： There are three 1 By 0 Surround . One 1 Not surrounded , Because it's on the border .

Example 2：

Input ： grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output ： 0
explain ： all 1 Are on the boundary or can reach the boundary .

Tips ：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] The value of is 0 or 1

# Breadth first traversal 
class Solution(object):
    def numEnclaves(self, grid):
        m = len(grid)
        n = len(grid[0])
        
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    queue = []
                    queue.append((i,j))
                    grid[i][j]=0
                    cnt = 1# Count the land quantity of each island 
                    flag = 1# Mark whether the island is land with boundary 
                    while queue:
                        x,y = queue[0]
                        queue.pop(0)
                        for xx,yy in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:
                            if not 0<=xx<m or not 0<=yy<n:
                                flag = 0# If there is land at the boundary , Then all the lands of this island are enclaves 
                            elif grid[xx][yy]==1:
                                queue.append((xx,yy))
                                grid[xx][yy]=0
                                cnt+=1
                    if flag:
                        result+=cnt
        return result              

# Depth-first traversal 
class Solution(object):
    def numEnclaves(self, grid):
        m = len(grid)
        n = len(grid[0])
        
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    stack = []
                    stack.append((i,j))
                    grid[i][j]=0
                    cnt = 1
                    flag = 1
                    while stack:
                        x,y = stack[-1]
                        stack.pop()
                        for xx,yy in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:
                            if not 0<=xx<m or not 0<=yy<n:
                                flag = 0
                            elif grid[xx][yy]==1:
                                stack.append((xx,yy))
                                grid[xx][yy]=0
                                cnt+=1
                    if flag:
                        result+=cnt
        return result