Python DFS without change grid


  • 0
    L
    def maxAreaOfIsland(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            l_row, l_column = len(grid), len(grid[0])
            visited = [[False] * l_column for _ in range(l_row)] #using visited to indicate if traversed before
            ret = [0]
            def traverse(i, j):
                if 0 <= i < l_row and 0 <= j < l_column and grid[i][j] == 1 and not visited[i][j]:
                    visited[i][j] = True
                    return 1 + traverse(i - 1, j) + traverse(i + 1, j) + traverse(i, j - 1) + traverse(i, j + 1)
                return 0
    
            for i in range(l_row):
                for j in range(l_column):
                    if not visited[i][j] and grid[i][j] == 1:
                        val = traverse(i, j)
                        ret[0] = max(val, ret[0])
            return ret[0]
    

Log in to reply
 

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