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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Connected Cells in a Grid
  5. Discussions

Connected Cells in a Grid

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 227 Discussions, By:

votes

Please Login in order to post a comment

  • dongyaoli
    6 years ago+ 4 comments

    A trick to avoid the boundary check: add an artificial boundary of 0 around the whole matrix.

    41|
    Permalink
    View more Comments..
  • wayn4bot
    4 years ago+ 10 comments

    I used Dfs

    #include <bits/stdc++.h>
    
    using namespace std;
    
    int a[100][100], vis[100][100];
    int r, c, TotalOne;
    
    int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
    int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
    
    bool check(int x, int y)
    {
        return (x >= 0 && x < r && y >= 0 &&  y < c);
    }
    
    void dfs(int i, int j)
    {
        TotalOne++;
        vis[i][j] = 1;
        for(int k = 0; k < 8; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
    
            if(check(x, y) && vis[x][y] == 0 && a[x][y] == 1)
                dfs(x, y);
        }
    }
    
    int main()
    {
        cin >> r >> c;
        for(int i = 0; i < r; i++)
            for(int j = 0; j < c; j++)
                cin >> a[i][j];
    
        int mx = INT_MIN;
        for(int i = 0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                if(vis[i][j] == 0 && a[i][j] == 1)
                {
                    TotalOne = 0;
                    dfs(i, j);
    
                    if(TotalOne > mx)
                        mx = TotalOne;
                }
            }
        }
    
        cout << mx;
    
        return 0;
    }
    
    29|
    Permalink
    View more Comments..
  • RodneyShag
    5 years ago+ 5 comments

    Java solution - passes 100% of test cases

    To keep track of visited grid cells, just mark the original grid cell with a 0. This simplifies the code.

    import java.util.Scanner;
    import java.util.ArrayList;
    
    /* Tips:
    1) Instead of using a "boolean[][] visited" array, we alter our original grid
    2) Dont create a 2-D "Point" or "Cell" class. It's not necessary.
    */
    public class Solution {
        
        private static int rows; // here for convenience
        private static int cols; // here for convenience
        
        public static void main(String[] args) {
            /* Read and save grid */
            Scanner scan = new Scanner(System.in);
            rows = scan.nextInt();
            cols = scan.nextInt();
            int grid[][] = new int[rows][cols];
            for (int grid_i = 0; grid_i < rows; grid_i++) {
                for (int grid_j = 0; grid_j < cols; grid_j++) {
                    grid[grid_i][grid_j] = scan.nextInt();
                }
            }
            scan.close();
    
            System.out.println(largestRegion(grid));
        }
        
        /* Returns the size of the largest region */
        public static int largestRegion(int [][] grid) {
            int maxRegion = 0;
            
            /* From each filled cell, find the largest region from that cell */
            for (int row = 0; row < rows; row++) {
                for (int col = 0; col < cols; col++) {
                    if (grid[row][col] == 1) {
                        int size = findLargestRegion(grid, row, col);
                        maxRegion = Math.max(maxRegion, size);
                    }
                }
            }
            return maxRegion;
        }
        
        private static int findLargestRegion(int [][] grid, int row, int col) {
            /* Pro tip: put boundary checks at top of recursive call, 
                        instead of before doing recursive call */
            if (row < 0 || row >= rows || col < 0 || col >= cols) {
                return 0;
            } else if (grid[row][col] == 0) {
                return 0;
            }
    
            grid[row][col] = 0; // we alter the original matrix here
            int size = 1;       // 1 accounts for our size
            
            /* Accounts recursively for neighbors sizes */
            for (int r = row - 1; r <= row + 1; r++) {
                for (int c = col - 1; c <= col + 1; c++) {
                    size += findLargestRegion(grid, r, c);
                }
            }
    
            return size;
        }
    }
    

    From my HackerRank Java solutions.

    20|
    Permalink
    View more Comments..
  • yashtekena
    6 years ago+ 2 comments

    My solution using floodfill in Python:

    n=int(input())
    m=int(input())
    def floodfill(i,j):
        if i>=n or j>=m or mat[i][j]==-1 or mat[i][j]==0 or i<0 or j<0:
            return 0
        else:
            mat[i][j]=-1
            return 1+(floodfill(i+1,j)+floodfill(i-1,j)+floodfill(i,j+1)+floodfill(i,j-1)+floodfill(i+1,j-1)+floodfill(i+1,j+1)+floodfill(i-1,j-1)+floodfill(i-1,j+1))
    
    mat=[]
    res=-999
    for i in range(n):
        mat.append([int(x) for x in input().split()]) 
    
    for i in range(n):
        for j in range(m):
            res=max(res,floodfill(i,j))
    print(res)        
    
    11|
    Permalink
  • crisrichm
    7 years ago+ 2 comments

    Solved with Union/Find

    7|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature