DFS: Connected cell in a grid

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

DFS: Connected cell in a grid

Post by dendiz » Wed Oct 10, 2018 9:43 pm

solution to the problem at

https://www.hackerrank.com/challenges/c ... id/problem

Code: Select all

def get_biggest_region(h, w, grid):
    max = 0
    for y in range(h):
        for x in range(w):
            queue = []
            queue.append([x,y])
            lmax = 0
            if grid[y][x] == 1:
                marker += 1
                while len(queue) > 0:
                    cur = queue.pop()
                    lx = cur[0]
                    ly = cur[1]
                    if grid[ly][lx] == 1:
                        lmax += 1
                        grid[ly][lx] = 'x'
                        for i in range(-1,2):
                            for j in range(-1,2):
                                if i == 0 and j == 0: continue
                                if lx + i < 0 or lx + i > w - 1: continue
                                if ly + j < 0 or ly + j > h - 1: continue
                                queue.append([lx + i, ly + j])
                if lmax > max:
                    max = lmax

    return max        

import sys
n = int(raw_input().strip())
m = int(raw_input().strip())
grid = []
for grid_i in xrange(n):
    grid_temp = map(int, raw_input().strip().split(' '))
    grid.append(grid_temp)
print get_biggest_region(n,m,grid)

Post Reply