[leetcode] 1254 - count the number of closed Islands

Two dimensional matrix grid from 0 （ land ） and 1 （ water ） form . The island is made up of the largest 4 Connected in two directions 0 Group composed of , The closed island is a Completely from 1 Surround （ Left 、 On 、 Right 、 Next ） The island of .

Please return Close the island Number of .

Example 1：

Input ： grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output ： 2
explain ：
The islands in the gray area are closed Islands , Because the island is completely surrounded by water （ Namely be 1 The area surrounds ）.

Example 2：

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

Example 3：

Input ： g rid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output ： 2

Tips ：

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

# Breadth first traversal 
class Solution(object):
    def closedIsland(self, grid):
        n = len(grid)
        m = len(grid[0])
        landcount = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j]==0:
                    val = 1
                    grid[i][j]=1
                    queue=[]
                    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 not 0<=xx<n or not 0<=yy<m:
                                val=0
                            elif grid[xx][yy]==0:
                                grid[xx][yy]=1
                                queue.append((xx,yy))
                    landcount+=val
        return landcount

# Depth-first traversal 
class Solution(object):
    def closedIsland(self, grid):
        n = len(grid)
        m = len(grid[0])
        landcount = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j]==0:
                    val = 1
                    grid[i][j]=1
                    stack=[]
                    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 not 0<=xx<n or not 0<=yy<m:
                                val=0
                            elif grid[xx][yy]==0:
                                grid[xx][yy]=1
                                stack.append((xx,yy))
                    landcount+=val
        return landcount