Concise BFS python solution


  • 0
    Y
    class Solution:
        # @param {character[][]} grid
        # @return {integer}
        def numIslands(self, grid):
            if not grid or not grid[0]:
                return 0
            m = len(grid)
            n = len(grid[0])
    
            for i in range(0, m):
                grid[i] = list(grid[i])
    
            res = 0
            for i in range(0, m):
                for j in range(0, n):
                    if grid[i][j] == '1':
                        self.bfs(grid, i, j)
                        res += 1
            return res
    
        def bfs(self, grid, i, j):
            m, n = len(grid), len(grid[0])
    
            q = deque()
            q.append((i, j))
            while q:
                i, j= q[0]
                q.popleft()
    
                if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != '1':
                    continue
    
                grid[i][j] = '2'
                q.append((i - 1, j))
                q.append((i + 1, j))
                q.append((i, j - 1))
                q.append((i, j + 1))
    
            return

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.