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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. DFS: Connected Cell in a Grid
  2. Discussions

DFS: Connected Cell in a Grid

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 221 Discussions, By:

recency

Please Login in order to post a comment

  • fredydeltoro
    4 months ago+ 0 comments

    hey this my javascript solution i try to make a flag for every node that i found and all its connections have the same flag so with that flags it's more easy count the area. I think that the way to find neigbords could be better if someone could improve it i'll be glad to see your solution

    function maxRegion(grid) {
      const nodes = {}
      const weights = new Set()
      
       const findNeighbours = (current, node) => {
        const x = [-1,-1,-1,0,0,1,1,1]
        const y = [-1,0,1,-1,1,-1,0,1]
        for(let i=0; i < 8; i++){
          let nx = x[i] + current[0]
          let ny = y[i] + current[1]
          
          if((nx > -1 && nx < grid.length) && (ny > -1 && nx <= grid[0].length)){
            let el = grid[nx][ny]
            
            if(el === 1){
              nodes[node].push(node)
              grid[nx][ny] = node
              findNeighbours([nx, ny], node)
            }
          }
          
        }
      }
      
      let count = 1
      for(let i = 0; i< grid.length; i++){
        grid[i].forEach((el, index) =>{
          if(el === 1){
            let found = count + el
            nodes[found]= [found]
            grid[i][index] = found
            findNeighbours([i, index], found)
            weights.add(nodes[found].length)
            count+= 1
          }
        })
      }
        
      return [...weights].sort((a, b) => b - a)[0]
    }
    
    0|
    Permalink
  • puppyodie
    9 months ago+ 0 comments

    I put my python code, it is not the best solution, but it is what I can do. The basic concept is when you find the first '1', then try to find the next '1' with the sequence, up=> up, right=> right=>right, down=>down=>down, left=>left=>left, top. It is recursive and cannot handle massive data in one area.
    The things you need to be careful of are the border constraints. Otherwise, you will have the exception or miss the '1' on the border.

    def maxRegion(grid):
        # Write your code here
        print(grid)
        tcount=0
        count = 0
        for y in range(0,len(grid)):
            for x in range(0, len(grid[0])):
                print("grid["+str(y)+"]["+str(x)+"]="+ str(grid[y][x]))
                if grid[y][x]==1:
                    tcount = FindRound(y,x,grid)
                    print("tcount="+str(tcount))
                if tcount>count:
                    count=tcount    
        return count
                                    
                
    def FindRound(iy,ix,grid):
        print("call FindRound ix="+str(ix)+",iy="+str(iy))
        count = 1
        grid[iy][ix]=0
        #check up
        if (iy-1)>=0:
            if grid[iy-1][ix]==1:
                count+=FindRound((iy-1),ix,grid)
        #check up-right
        if (iy-1)>=0 and (ix+1)<len(grid[0]):
            if grid[iy-1][ix+1]==1:
                count+=FindRound(iy-1, ix+1,grid)
        #check right
        if (ix+1)<len(grid[0]):
            if grid[iy][ix+1]==1:
                count+=FindRound(iy,ix+1,grid)
        #check right-down
        if(ix+1)<len(grid[0]) and (iy+1)<len(grid):
            if grid[iy+1][ix+1]==1:
                count+=FindRound(iy+1,ix+1,grid)
        #check down
        if (iy+1)<len(grid):
            if grid[iy+1][ix]==1:
                count+=FindRound(iy+1,ix,grid)
        #check down-left
        if (iy+1)<len(grid) and (ix-1)>=0:
            if grid[iy+1][ix-1]==1:
                count+=FindRound(iy+1,ix-1,grid)
        #chekc left
        if(ix-1)>=0:
            if grid[iy][ix-1]==1:
                count+=FindRound(iy,ix-1,grid)
        #check left-up
        if(ix-1)>=0 and (iy-1)>0:
            if grid[iy-1][ix-1]==1:
                count+=FindRound(iy-1,ix-1,grid)
        
        return count
    
    -1|
    Permalink
  • CodeName777
    12 months ago+ 0 comments

    https://medium.com/p/a75c2d0e0080

    0|
    Permalink
  • erikw
    2 years ago+ 0 comments

    Simple Ruby full solution:

    def region_size(grid, row, col)
      return 0 unless row.between?(0, grid.length - 1) &&
                      col.between?(0, grid[0].length - 1) &&
                      grid[row][col] == 1
    
      grid[row][col] = 0
      (-1..1).map do |r|
        (-1..1).map do |c|
          region_size(grid, row + r, col + c)
        end.sum
      end.sum + 1
    end
    
    def max_region(grid)
      (0...grid.length).map do |row|
        (0...grid[0].length).map do |col|
          region_size(grid, row, col)
        end.max
      end.max
    end
    
    n = gets.to_i
    _m = gets.to_i
    grid = Array.new(n)
    n.times do |i|
      grid[i] = gets.split.map(&:to_i)
    end
    puts max_region(grid)
    
    0|
    Permalink
  • underrated880
    2 years ago+ 0 comments

    well

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy