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
  • 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 247 Discussions, By:

recency

Please Login in order to post a comment

  • sergej_panov
    6 days ago+ 0 comments

    Ruby:

    def cover_neighbours(i,j,m,n)
      return if i>=n || j>=m || i<0 || j<0
      return if @matrix[i][j] == 0
      
      @matrix[i][j] = 0
      @count += 1
      
      cover_neighbours(i+1,j,m,n)
      cover_neighbours(i-1,j,m,n)
      cover_neighbours(i,j+1,m,n)
      cover_neighbours(i,j-1,m,n)
      cover_neighbours(i+1,j-1,m,n)
      cover_neighbours(i-1,j+1,m,n)
      cover_neighbours(i+1,j+1,m,n)
      cover_neighbours(i-1,j-1,m,n)
    end
    
    
    def connectedCell(matrix)
      n = matrix.size
      m = matrix[0].size
      @matrix = matrix
      max_count = 0
      for i in 0..(n-1) do
        for j in 0..(m-1) do
          if @matrix[i][j] == 1
            @count = 0
            cover_neighbours(i,j,m,n)
            max_count = @count if @count > max_count
          end
        end
      end
      
      return max_count 
      
    end
    
    0|
    Permalink
  • kapilcodes
    1 week ago+ 0 comments

    **My Solution in C++ **

    PS: I didn't know DFS so I came out with my own approach

    Code:

    #include <bits/stdc++.h>
    
    using namespace std;
    #define printTime(t) cout << "\nTIME: " << (float) t/CLOCKS_PER_SEC << "\n";
    typedef long long ll;
    #define F first
    #define S second
    typedef vector<int> vi;
    #define pop_front() erase(0,1);
    
    const int mod = 1e9 + 7;
    
    int visited[10][10];
    vector<vector<int>> matrix(10,vector<int> (10,0));
    int ni, mi;
    int search(int i ,int j){
      int result = 1;
      visited[i][j] = 1;
    
    bool l, r, d, ld,rd, u,lu,ru;
    l = (j-1 >= 0) && (matrix[i][j-1]) ;
    r = (j+1 < mi) && (matrix[i][j+1]) ;
    ld = (j-1 >= 0 && i+1 < ni) && (matrix[i+1][j-1]); 
    rd = (j+1 < mi && i+1 < ni) && (matrix[i+1][j+1]);
    d =  (i+1 < ni) && (matrix[i+1][j]);
    u = (i-1 >= 0) && (matrix[i-1][j]);
    lu = (i-1 >= 0 && j-1 >= 0) && (matrix[i-1][j-1]);
    ru = (i-1 >= 0 && j+1 < mi) && (matrix[i-1][j+1]);
    if(l && !visited[i][j-1]){
      result += search(i,j-1);
    }
    if(r && !visited[i][j+1]){
      result += search(i,j+1);
    }
    if(d && !visited[i+1][j]){
      result += search(i+1,j);
    }
    if(ld && !visited[i+1][j-1]){
      result += search(i+1,j-1);
    }
    if(rd && !visited[i+1][j+1]){
      result += search(i+1,j+1);
    }
    if(u && !visited[i-1][j])
    {
      result += search(i-1, j);
    }
    if(lu && !visited[i-1][j-1])
    {
      result += search(i-1, j-1);
    }
    if(ru && !visited[i-1][j+1])
    {
      result += search(i-1, j+1);
    }
    
    
    
    return result;
    }
    
    int connectedCell(vector<vector<int>> matrix) {
    
    int count = INT_MIN;
    for(int i = 0; i < ni; i++){
      for(int j = 0; j < mi; j++){
        if(!visited[i][j] && matrix[i][j]){
                 int temp = search(i,j);
                 count = max(count, temp);
                 // printf("[%d, %d] | %d\n",i,j,temp);
                // cout << "[" << i << ","<<j<<"] | "<<temp << '\n';
                }
      }
    }
    return count;
    }
    
    int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1, n, m,k;
    //cin >> t;
    
    while(t--){
    cin >> ni >> mi;
    for(int i = 0; i < ni; i++){
      for(int j = 0; j < mi ; j++)
            cin >> matrix[i][j];
    }
    cout << connectedCell(matrix) << endl << endl;
    
    // for(int i = 0; i < ni; i++)
    // {
    //   for(int j = 0; j < mi; j++)
    //       cout << visited[i][j] << ' ';
    //     cout << endl;
    // }
    }
    
    return 0;}
    
    0|
    Permalink
  • yashparihar729
    3 weeks ago+ 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp Click Here

    0|
    Permalink
  • dcd26
    4 weeks ago+ 0 comments

    BFS

    #include<bits/stdc++.h>
    using namespace std;
    
    #define ROW 10
    #define COL 10
    
    int n, m;
    int grid[ROW][COL];
    bool vis[ROW][COL];
    int ans = 0;
    
    // Direction vectors
    vector<vector<int>> dir{{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
    
    // Function to check if a cell is be visited or not
    bool isValid(bool vis[][COL], int row, int col){
        if (row < 0 || row >= ROW || col < 0 || col >= COL) return false;
        if (vis[row][col]) return false;
        return true;
    }
    
    // Function to perform the BFS
    void BFS(int grid[][COL], bool vis[][COL], int row, int col){
        int tem = 0;
        queue<pair<int, int>> q;
        q.push({row, col});
        vis[row][col] = true;
        while (!q.empty()){
            pair<int, int> fro = q.front();
            int x = fro.first;
            int y = fro.second;
            q.pop(); tem++;
            for (auto d : dir){
                int neix = x + d[0];
                int neiy = y + d[1];
                if (isValid(vis, neix, neiy) && grid[neix][neiy]){
                    q.push({neix, neiy});
                    vis[neix][neiy] = true;
                    grid[neix][neiy] = 0;
                }
            }
        }
        ans = max(ans, tem);
    }
    
    // Driver code
    int main(){
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) 
                cin >> grid[i][j];
        memset(vis, false, sizeof(vis));
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++)
                if (grid[i][j])
                    BFS(grid, vis, i, j);
        cout << ans;
    }
    
    0|
    Permalink
  • danielb143
    1 month ago+ 1 comment

    Here's a simple solution Go:

    func rSearch(matrix *[][]int32, r, c, rows, cols int32) int32 {
        sum := int32(1)
        (*matrix)[r][c] = int32(2) // mark cell as visited
        for i := int32(-1); i <= 1; i++ {
            for j := int32(-1); j <= 1; j++ {
                if (i == 0 && j == 0) ||
                r + i < 0 || r + i >= rows ||
                c + j < 0 || c + j >= cols {
                    continue
                }
                if (*matrix)[r+i][c+j] == 1 {
                    sum += rSearch(matrix, r + i, c + j, rows, cols)
                }
            }
        }
        return sum
    }
    
    func connectedCell(matrix [][]int32) int32 {
        // - iterate over matrix left to right top to bottom
        // - when finding a cell, recursively explore the unvisited neighbors
        rows := int32(len(matrix))
        cols := int32(len(matrix[0]))
        var mSize int32
        for r := int32(0); r < rows; r++ {
            for c := int32(0); c < cols; c++ {
                if matrix[r][c] == 1 {
                    size := rSearch(&matrix, r, c, rows, cols)
                    if size > mSize {
                        mSize = size
                    }
                }
            }
        }
        return mSize
    }
    
    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