HackerRank Connected Cells in a Grid problem solution

In this HackerRank Connected Cells in a Grid problem solution we have given an n x m matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.

Problem solution in Python.

m_rows, n_cols = int(input()), int(input())
matrix = []
for i in range(0, m_rows):
    matrix.append(list(map(int, input().split())))
cellCtr = 0

def maxConnectedGrid():
    global cellCtr
    maxCtr = 0
    for i in range(0, m_rows):
        for j in range(0, n_cols):
            dfs(i, j)
            if (cellCtr > maxCtr):
                maxCtr = cellCtr
            cellCtr = 0
    return maxCtr

def dfs(row, col):
    global cellCtr
    if(row < 0 or row >= m_rows or col < 0 or col >= n_cols or matrix[row][col] == 0):
        return
    
    matrix[row][col] = 0
    cellCtr += 1
    
    dfs(row-1, col-1) ;  dfs(row-1, col) ;   dfs(row-1, col+1)
    dfs(row,   col-1) ;                      dfs(row,   col+1)
    dfs(row+1, col-1) ;  dfs(row+1, col) ;   dfs(row+1, col+1)
    
    
print(maxConnectedGrid())

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    private static int[]nav={-1,0,1};
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in=new Scanner(System.in);
        int m=in.nextInt();
        int n=in.nextInt();
        
        int a[][]=new int[m][n];
        boolean visited[][]=new boolean [m][n];
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                a[i][j]=in.nextInt();
            }
        }
        
        int max=0;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if( !visited[i][j] ){
                    int region=region(visited, a,i,j,m,n);
                                   
                    max=Math.max(max,region);
                }
            }
        }
       
        System.out.println(max);
    }
    
    private static int region(boolean[][]visited, int [][]a,int row, int col, int m,int n){
        if(row>=m || col >=n || row<0 || col<0 || a[row][col]==0 || visited[row][col])return 0;
        visited[row][col]=true;
        int region=1;
        for(int r:nav){
            for(int c:nav){
                region+=region(visited,a,row+r,col+c,m,n);
            }
        }
        
        return region;
    }
    
}

{"mode":"full","isActive":false}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int m, n;

int visit (int i, int j , short*  ma) {
    
    
    if (i<0 || i>=m || j< 0 || j>= n || ma[i*n + j]==0)
        return 0;
    else {
        int found=1;
        //cout << i << " " << j << "\n";
        ma[i*n + j]=0;
        found += visit(i-1, j-1, ma);
        found += visit(i-1, j, ma);
        found += visit(i-1, j+1, ma);
        found += visit(i, j+1, ma);
       
        found += visit(i, j-1, ma);
        found += visit(i+1, j+1, ma);
        found += visit(i+1, j, ma);
        found += visit(i+1, j-1, ma);
        return found;
        
    }
}

int main() {
    
    cin >> m;
    cin >> n;
    int i,j;
    short matrix[m*n];
    for (i=0; i<m; i++)
        for (j=0; j<n; j++) {
        cin >> matrix[i*n + j];
        
    }
    
    
    i=0;
    j=0;
    int max=0;
    while (i<m && j<n) {
        //cout << "starting\n";
        while (matrix[i*n + j] == 0) {
            j++;
            if (j > n) {
                i++;
                j=0;
            }
            if (i > m)
                break;
        }
        if (i > m)
            break;
        
        int found=visit(i,j,matrix);
        if (found > max )
            max=found;
        
    }
    cout << max << "\n";
    return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int **matrix=0, m, n;
static int direction[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};

int valid_cell(int i, int j) {
    if (i<0 || i>=m || j<0 || j>=n)
        return 0;
    return matrix[i][j];
}

int find_region_count(int i, int j){
    int n=0, len=0, new_i, new_j;
    matrix[i][j]=0;
    for(n=0;n<8;n++){
        new_i = i+direction[n][0];
        new_j = j+direction[n][1];
        if (valid_cell(new_i, new_j)) {
            len += find_region_count(new_i, new_j);
        }
    }
    len++;
    return len;
}

int main() {

    int i, j, cnt, max=0;
    
    scanf("%d %d", &m, &n);
    matrix = malloc(sizeof(int *) * m);
    for(i=0;i<m;i++) {
        matrix[i] = malloc(sizeof(int) *n);
    }
    
    for(i=0;i<m;i++) {
        for(j=0;j<n;j++){
            scanf("%d", &matrix[i][j]);
        }
    }
    
    for(i=0;i<m;i++) {
        for(j=0;j<n;j++){
            if (matrix[i][j]) {
                cnt = find_region_count(i, j);
                if (cnt > max) {
                    max = cnt;
                }
            }
        }
    }
    printf("%d", max);
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}

{"mode":"full","isActive":false}