Python BFS solution


  • 0
    F
    def maxAreaOfIsland(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            res = 0
            for i in xrange(len(grid)):
                for j in xrange(len(grid[0])):
                    if grid[i][j]:
                        res = max(res, self.bfs(grid, i, j))
            return res
        
    def bfs(self, grid, i, j):
            queue = [(i, j)]
            grid[i][j] = 0
            res = 0
            while queue:
                x, y = queue.pop(0)
                res += 1
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny]:
                        grid[nx][ny] = 0
                        queue.append((nx, ny))
            return res
    

Log in to reply
 

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