# HackerRank DFS: Connected Cell in a Grid solution

In this HackerRank DFS: Connected Cell in a Grid Interview preparation kit problem there is Given an n x m matrix, find and print the number of cells in the largest region in the matrix.

## Problem solution in Python programming.

```def getAdjacentNodes(matrix, i, j):
s = set()
if i - 1 >= 0:
if matrix[i-1][j] == 1:
s = s.union([(i-1, j)])
if j - 1 >= 0:
if matrix[i-1][j-1] == 1:
s = s.union([(i-1, j-1)])

if j + 1 < len(matrix[i]):
if matrix[i-1][j+1] == 1:
s = s.union([(i-1, j+1)])

if i + 1 < len(matrix):
if matrix[i+1][j] == 1:
s = s.union([(i+1, j)])
if j - 1 >= 0:
if matrix[i+1][j-1] == 1:
s = s.union([(i+1, j-1)])

if j + 1 < len(matrix[i]):
if matrix[i+1][j+1] == 1:
s = s.union([(i+1, j+1)])

if j - 1 >= 0:
if matrix[i][j-1] == 1:
s = s.union([(i, j-1)])

if j + 1 < len(matrix[i]):
if matrix[i][j+1] == 1:
s = s.union([(i, j+1)])

return s

g = {}
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 1:
g[(i, j)] = getAdjacentNodes(matrix, i, j)
return g

def dfs(graph):
def helper(start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
stack.extend(graph[vertex] - visited)
return len(visited)
return helper

def getBiggestRegion(grid):
sizes = []
gdfs = dfs(graph)
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 1:
sizes.append(gdfs((i, j)))
return max(sizes)

n = int(input().strip())
m = int(input().strip())
grid = []
for grid_i in range(n):
grid_t = list(map(int, input().strip().split(' ')))
grid.append(grid_t)
print(getBiggestRegion(grid))```

## Problem solution in Java Programming.

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

static boolean[] marked;
static int[] id;
static int[] size;
static int count;
private static int largestConnectedComponentCount(Graph g) {
List<Integer> nodes = new ArrayList<>();
int i = 0;
for (boolean e : g.enabled) {
i++;
}

marked = new boolean[g.enabled.length];
id = new int[g.enabled.length];
size = new int[g.enabled.length];
count = 0;
for (int v : nodes) {
if (!marked[v]) {
dfs(g, v);
count++;
}
}

return Arrays.stream(size).max().orElse(0);
}

// depth-first search
private static void dfs(Graph g, int v) {
marked[v] = true;
id[v] = count;
size[count]++;
.stream()
.filter(w -> !marked[w])
.forEach(w -> dfs(g, w));
}

private static class Graph {
boolean[] enabled;

Graph(int size) {
enabled = new boolean[size];
for (int i = 0; i < size; i++) {
}
}
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int i = 0;
Graph g = new Graph(n * m);
for(int row = 0; row < n; row++){
for(int col = 0; col < m; col++) {
int val = in.nextInt();
if (val == 1) {
g.enabled[i] = true;

int prev = i - 1;
int upLeft = i - m - 1;
int up = i - m;
int upRight = i - m + 1;
if (col > 0 && g.enabled[prev]) {
}
if (col > 0 && row > 0 && g.enabled[upLeft]) {
}
if (row > 0 && g.enabled[up]) {
}
if (col < m - 1 && row > 0 && g.enabled[upRight]) {
}
}
i++;
}
}

System.out.println(largestConnectedComponentCount(g));

}
}```

### Problem solution in C++ programming.

```#include<bits/stdc++.h>
using namespace std;
int a[10][10];

int count(int i,int j,int n, int m)
{
if(a[i][j] == 0)
return 0;
if(i<0 or j<0 or i>= n or j >=m)
return 0;
if(a[i][j] == 1)
{
a[i][j]--;
}

}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
int max = -1,ans;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
ans = count(i,j,n,m);
if(ans > max)
max = ans;
}
cout<<max;
return 0;
}```

### Problem solution in C programming.

```#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define RUN_TEST_CASES(VAR) int VAR##_total; scanf("%d", & VAR##_total); \
for(int VAR=1; VAR<=VAR##_total; ++VAR)

typedef unsigned long long ull;

int get_area_size(int matrix[10][10], int rows, int cols, int row, int col)
{
if (row < 0 || row >= rows) return 0;
if (col < 0 || col >= cols) return 0;
if (matrix[row][col] != 1) return 0;

matrix[row][col] = 0; // visited

return 1
+ get_area_size(matrix, rows, cols, row - 1, col - 1)
+ get_area_size(matrix, rows, cols, row - 1, col)
+ get_area_size(matrix, rows, cols, row - 1, col + 1)
+ get_area_size(matrix, rows, cols, row, col - 1)
+ get_area_size(matrix, rows, cols, row, col + 1)
+ get_area_size(matrix, rows, cols, row + 1, col - 1)
+ get_area_size(matrix, rows, cols, row + 1, col)
+ get_area_size(matrix, rows, cols, row + 1, col + 1)
;
}

int main()
{
#ifdef _DEBUG
char FNAME[250];
strcpy(FNAME, __FILE__);
strcpy(strchr(FNAME, '.'), ".txt");
freopen(FNAME, "rt", stdin);
#endif

int matrix[10][10];

int rows, cols;
scanf("%d %d", &rows, &cols);

for (int row = 0; row < rows; ++row)
for (int col = 0; col < cols; ++col)
scanf("%d", &matrix[row][col]);

int largest_area = 0;

for (int row = 0; row < rows; ++row)
{
for (int col = 0; col < cols; ++col)
{
if (matrix[row][col] != 1) continue;
int area_size = get_area_size(matrix, rows, cols, row, col);
if (area_size > largest_area)
largest_area = area_size;
}
}

printf("%d", largest_area);
}```

### Problem solution in JavaScript programming.

```process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
input_stdin += data;
});

process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});

return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

var isValid = function(x, y, n, m) {
return (x >= 0 && y >= 0 && x < n && y < m);
}
var visit = function(x, y, grid, visited, n, m) {
if (grid[x][y] === 1 && !visited[x][y]) {
var count = 1;
visited[x][y] = true;
for (var i = x - 1; i <= x + 1; i++) {
for (var j = y - 1; j <= y + 1; j++) {
if (isValid(i, j, n, m)) {
count += visit(i, j, grid, visited, n, m);
}
}
}
return count;
} else {
return 0;
}
}

function main() {
var grid = [];
for(grid_i = 0; grid_i < n; grid_i++){
grid[grid_i] = grid[grid_i].map(Number);
}

var visited = [];
for (var i = 0; i < grid.length; i++) {
visited.push([]);
}

var max = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < m; j++) {
var count = visit(i, j, grid, visited, n, m);
max = Math.max(count, max);
}
}
console.log(max);
}```