# 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}