[leetcode] 200 number of islands

Here you are ‘1’（ land ） and ‘0’（ water ） A two-dimensional mesh of , Please calculate the number of islands in the grid .

Islands are always surrounded by water , And each island can only be combined by horizontal direction / Or a vertical connection between adjacent lands .

Besides , You can assume that all four sides of the mesh are surrounded by water .

Example 1：

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

Example 2：

Input ： grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
Output ： 3

Tips ：

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

notes ：
In case of 1 Immediately set as 0, Don't wait from the queue or Take it out of the stack and set it to 0, It will cause a large number of coordinate points to be repeated into the team or Push , Make the time exceed the limit ！！！

## Breadth first traversal 
class Solution(object):
    def numIslands(self, grid):
        n = len(grid)# Get array length 
        if n == 0:
            return 0
        m = len(grid[0])# Get array width 
        cnt = 0# Number of Islands 
        queue = []# Queue container 
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":# If you meet land, start traversing 
                    cnt+=1# The number of islands plus one 
                    grid[i][j]="0"# Set as 0, Avoid repeated visits to 
                    queue.append((i,j))# Join the queue , To traverse the 
                    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)]:# Traverse in four directions 
                            if 0<=xx<n and 0<=yy<m and grid[xx][yy]=="1":
                                grid[xx][yy]="0"
                                queue.append((xx,yy))
        return cnt

## Depth-first traversal 
class Solution(object):
    def numIslands(self, grid):
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        cnt = 0
        stack = []
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":
                    cnt+=1
                    grid[i][j]="0"
                    stack.insert(0,(i,j))
                    while stack:
                        x,y = stack[0]
                        stack.pop(0)
                        for xx,yy in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                            if 0<=xx<n and 0<=yy<m and grid[xx][yy]=="1":
                                grid[xx][yy]="0"
                                stack.insert(0,(xx,yy))
        return cnt