python islands - EASY TO UNDERSTAND - 95%


  • 0
    S
    class Solution(object):
        def bfs(self, grid, row, col, maxrows, maxcols):
            queue = [(row,col)]
            length = 1
            
            while length:
    
                neighbours = []
                for cell in queue:
    
                    r,c = cell[0], cell[1]
                    grid[r][c] = "X"
                    # top
                    if r != 0:
                        if grid[r-1][c] == "1":
                            grid[r-1][c] = "X"
                            neighbours.append((r-1, c))
                    # down
                    if r != maxrows - 1:
                        if grid[r+1][c] == "1":
                            grid[r+1][c] = "X"
                            neighbours.append((r+1, c))
                    # left
                    if c != 0:
                        if grid[r][c-1] == "1":
                            grid[r][c-1] = "X"
                            neighbours.append((r, c-1))
                    # right
                    if c != maxcols - 1:
                        if grid[r][c+1] == "1":
                            grid[r][c+1] = "X"
                            neighbours.append((r, c+1))
                
                queue = neighbours
                length = len(queue)
            
            return 1
        
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            rows = len(grid)
            if rows:
                cols = len(grid[0])
            else:
                return 0
            island = 0
            
            for r in range(rows):
                for c in range(cols):
                    if grid[r][c] == "1":
                        island += self.bfs(grid, r, c, rows, cols)
            
    
                
            return island
    

Log in to reply
 

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