We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. DFS: Connected Cell in a Grid
  2. Discussions

DFS: Connected Cell in a Grid

  • sunil_sharma509
     + 0 comments

    Here is my Python 3 solution

    def exploreSize(grid,r,c,visited):
    rowInBound = r >= 0 and r < len(grid)
    colInBound = c >= 0 and c < len(grid[0])
    pos = str(r)+','+str(c)
    if not rowInBound or not colInBound: return 0
    if pos in visited: return 0
    if grid[r][c] == 0: return 0
    visited.add(pos)
    size = 1
    size += exploreSize(grid,r-1,c,visited)
    size += exploreSize(grid,r+1,c,visited)
    size += exploreSize(grid,r,c-1,visited)
    size += exploreSize(grid,r,c+1,visited)
    size += exploreSize(grid,r-1,c-1,visited)
    size += exploreSize(grid,r+1,c+1,visited)
    size += exploreSize(grid,r-1,c+1,visited)
    size += exploreSize(grid,r+1,c-1,visited)
    return size
    
def maxRegion(grid):
    # Write your code here
    visited = set()
    maxSize = -1
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            size = exploreSize(grid,r,c,visited)
            if size > maxSize: maxSize = size
                
    return maxSize