[LeetCode] Number of Islands (Python)

 

 

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        islands = 0
        M = len(grid)
        N = len(grid[0])
        visited = [[False] * N for _ in range(M)]
        
        def bfs(x, y):
            dx = [-1, 0, 0, 1]
            dy = [0, -1, 1, 0]
            visited[x][y] = True
            q = deque()
            q.append((x, y))
            while q:
                cur_x, cur_y = q.popleft()
                for i in range(4):
                    nx, ny = cur_x + dx[i], cur_y + dy[i]
                    if nx >= 0 and nx < M and ny >= 0 and ny < N:
                        if grid[nx][ny] == "1" and not visited[nx][ny]:
                            visited[nx][ny] = True
                            q.append((nx, ny))
                            
        for i in range(M):
            for j in range(N):
                if grid[i][j] == "1" and not visited[i][j]:
                    bfs(i, j)
                    islands += 1
        return islands