class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid)==0:return 0
        directions=[(-1,0),(1,0),(0,-1),(0,1)]
        m=len(grid)
        n=len(grid[0])
        cnt=0
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    cnt+=1
                    grid[i][j]='0'
                    queue=[(i,j)]
                    while queue:
                        next_queue=[]
                        for old_x,old_y in queue:
                            for direction in directions:
                                new_x,new_y=old_x+direction[0],old_y+direction[1]
                                if 0<=new_x<m and 0<=new_y<n and grid[new_x][new_y]==&#39;1&#39;:
                                    next_queue.append((new_x,new_y))
                                    grid[new_x][new_y]=&#39;0&#39;
                        queue=next_queue
        return cnt

BFS的标记一入队就要标记，防止重复入队的情况