HackerRank Connected Cells in a Grid Solution
In this post, we will solve HackerRank Connected Cells in a Grid Problem Solution.
Consider a matrix where each cell contains either a 0 or a 1. Any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. In the following grid, all cells marked X are connected to the cell marked Y.
XXX
XYX
XXX If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.
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.
For example, there are two regions in the following 3 x 3 matrix. The larger region at the top left contains 3 cells. The smaller one at the bottom right contains 1.
110
100
001Function Description
Complete the connectedCell function in the editor below.
connected Cell has the following parameter(s):
- int matrix[n][m]: matrix[i] represents the ¿th row of the matrix
Returns
-int: the area of the largest region
Input Format
The first line contains an integer n, the number of rows in the matrix.
The second line contains an integer m, the number of columns in the matrix.
Each of the next n lines contains m space-separated integers matrix[i][j].
Sample Input
STDIN Function
----- --------
4 n = 4
4 m = 4
1 1 0 0 grid = [[1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 0]]
0 1 1 0
0 0 1 0
1 0 0 0Sample Output
5
Explanation
The diagram below depicts two regions of the matrix. Connected regions are filled with X or Y. Zeros are replaced with dots for clarity.
X X . .
. X X .
. . X .
Y . . .
The larger region has 5 cells, marked X.
Connected Cells in a Grid C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int m, n, k, a[20][20];
void
recu(int i, int j)
{
// printf("%d %d\n", i, j);
if (i - 1 >= 0 && a[i-1][j] == 1) {
a[i-1][j] = k;
recu(i-1, j);
}
if (i + 1 < m && a[i+1][j] == 1) {
a[i+1][j] = k;
recu(i+1, j);
}
if (j - 1 >= 0 && a[i][j-1] == 1) {
a[i][j-1] = k;
recu(i, j-1);
}
if (j + 1 < n && a[i][j+1] == 1) {
a[i][j+1] = k;
recu(i, j+1);
}
if (j + 1 < n && i + 1 < m && a[i+1][j+1] == 1) {
a[i+1][j+1] = k;
recu(i+1, j+1);
}
if (j - 1 >= 0 && i + 1 < m && a[i+1][j-1] == 1) {
a[i+1][j-1] = k;
recu(i+1, j-1);
}
if (j - 1 >= 0 && i - 1 > 0 && a[i-1][j-1] == 1) {
a[i-1][j-1] = k;
recu(i-1, j-1);
}
if (j + 1 < n && i - 1 > 0 && a[i-1][j+1] == 1) {
a[i-1][j+1] = k;
recu(i-1, j+1);
}
}
int main() {
int i, j, *arr;
scanf ("%d%d", &m, &n);
for(i= 0; i < m; i++) {
for(j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
k = 2;
for(i= 0; i < m; i++) {
for(j = 0; j < n; j++) {
if (a[i][j] == 1) {
a[i][j] = k;
recu(i,j);
k++;
}
}
}
arr = (int *)calloc(1, k * sizeof(int));
for(i= 0; i < m; i++) {
for(j = 0; j < n; j++) {
if (a[i][j] != 0) {
arr[a[i][j]] ++;
}
//printf("%d ", a[i][j]);
}
//printf("\n");
}
int max = -1;
for (i = 0; i < k; i ++) {
if (max < arr[i])
max = arr[i];
}
free(arr);
printf("%d\n", max);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}Connected Cells in a Grid C++ Solution
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int cc;
void rec(vector<vector<int> > &A, int i, int j, int prevC, int newC)
{
if (i < 0 || i >= A.size() || j < 0 || j >= A[0].size())
{
return;
}
if (A[i][j] != prevC)
{
return;
}
cc++;
A[i][j] = newC;
rec(A, i + 1, j, prevC, newC);
rec(A, i - 1, j, prevC, newC);
rec(A, i, j + 1, prevC, newC);
rec(A, i, j - 1, prevC, newC);
rec(A, i + 1, j + 1, prevC, newC);
rec(A, i + 1, j - 1, prevC, newC);
rec(A, i - 1, j + 1, prevC, newC);
rec(A, i - 1, j - 1, prevC, newC);
}
int main(void)
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int m;
cin >> m;
int n;
cin >> n;
vector<vector<int> > A(m, vector<int>(n));
for (int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
cin >> A[i][j];
}
}
int cmx = INT_MIN;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cc = 0;
rec(A, i, j, 1, 2);
cmx = max(cmx, cc);
}
}
cout << cmx << endl;
return 0;
}Connected Cells in a Grid C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
public class DepthFirstSearchGraph
{
// node class to store the state of each vertex while performing depth-first-search
public class Node
{
public string name { set; get; }
public bool visited { set; get; }
public Node()
{
this.name = String.Empty;
this.visited = false;
}
}
// the maximum number of nodes this graph can contain
public int maxNodes;
// the adjacents lookup table that will help us navigate the graph
public int[,] adjacents;
// the vertices that shall be the nodes of our graph
public List<Node> nodes;
public DepthFirstSearchGraph(int maxNodes)
{
this.maxNodes = maxNodes;
this.nodes = new List<Node>(maxNodes);
this.adjacents = new int[maxNodes, maxNodes];
// intializing all adjacent values as 0
for (int i = 0; i < maxNodes; i++)
for (int j = 0; j < maxNodes; j++)
adjacents[i, j] = 0;
}
// function Dfs (depth first search):
// 1. navigating all graphs starting by a default node
// 2. each node traversed is pushed into a stack (to know our way back to the original node)
// 3. at a dead end, we go back, and find the next adjacent node (through the adjacents matrix)
// 4. finally, we get all graphs and we find the maximum graph by points (number of nodes traversed)
public void Dfs(int node)
{
bool allGraphNavigated = false;
List<int> graphAreas = new List<int>();
while (!allGraphNavigated)
{
int area = 0;
int nextNode = node;
Stack<int> visits = new Stack<int>();
visits.Push(nextNode);
nodes[nextNode].visited = true;
area++;
while (visits.Count > 0)
{
nextNode = GetUnVisitedAdjacent(nextNode);
//Console.WriteLine("adjacent is: {0}", nextNode);
if (nextNode != -1)
{
area++;
visits.Push(nextNode);
nodes[nextNode].visited = true;
//Console.WriteLine("nextVertex is: {0}", nextNode);
}
else
{
//Console.WriteLine("popped is: {0}", visits.Peek());
nextNode = visits.Pop();
}
}
graphAreas.Add(area);
// we are trying to know if there any unvisited not, so we start a new grap traversing
if (nodes.Where(n => !n.visited).Any())
node = nodes.IndexOf(nodes.Where(n => !n.visited).First());
else
allGraphNavigated = true;
}
Console.WriteLine(graphAreas.Max());
}
// function AddVertex: inserting a new vertex, with the name (index of last vertex + 1)
public void AddNode(String nodeName)
{
nodes.Add(new Node() { name = nodeName });
}
// function AddAdjacent: making the connection between two nodes to form an adjacent (node 0 <---> node 1)
public void AddAdjacent(int node, int adjacent)
{
adjacents[node, adjacent] = 1;
adjacents[adjacent, node] = 1;
}
// function AddAdjacent: making the connection between two nodes to form an adjacent by named nodes (node 0 <---> node 1)
public void AddAdjacent(string node, string adjacent)
{
int nodeIndex = nodes.IndexOf(nodes.Where(n => n.name == node).First());
int adjacentIndex = nodes.IndexOf(nodes.Where(n => n.name == adjacent).First());
adjacents[nodeIndex, adjacentIndex] = 1;
adjacents[adjacentIndex, nodeIndex] = 1;
}
// function GetUnVisitedAdjacent: looking up the adjacent matrix to find the next adjacent point to "vertex" that hasn't been visited
private int GetUnVisitedAdjacent(int node)
{
if (node >= 0)
for (int i = 0; i < maxNodes; i++)
if (adjacents[node, i] == 1 && !nodes[i].visited)
return i;
return -1;
}
}
static void Main(string[] args)
{
// A depth first search algorith would work fine in the case of this problem. It was challenging because:
// 1. The "adjacents" were not provided, and I had to extract them (provided as a form of a matrix)
// 2. I have to calculate all graph paths in order get the biggest region
int nodes = 0;
int rows = int.Parse(Console.ReadLine());
int columns = int.Parse(Console.ReadLine());
int[,] matrix = new int[rows, columns];
// getting input and counting the nodes
for (int i = 0; i < rows; i++)
{
int[] values = Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
for (int j = 0; j < values.Length; j++)
{
nodes++;
matrix[i, j] = values[j];
}
}
DepthFirstSearchGraph graph = new DepthFirstSearchGraph(nodes);
// adding named nodes in order to refer to them later on when adding the adjacents
for (int i = 0; i < rows; i++)
for (int j = 0; j < columns; j++)
if (matrix[i, j] == 1)
graph.AddNode(i + "." + j);
// extracting the adjacents, which got me into two traps (two fault submissions)
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
if (matrix[i, j] == 1)
{
if (i + 1 < rows)
if (matrix[i + 1, j] == 1)
graph.AddAdjacent(i + "." + j, (i + 1) + "." + j);
if (j + 1 < columns)
if (matrix[i, j + 1] == 1)
graph.AddAdjacent(i + "." + j, i + "." + (j + 1));
if (i + 1 < rows && j + 1 < columns)
if (matrix[i + 1, j + 1] == 1)
graph.AddAdjacent(i + "." + j, (i + 1) + "." + (j + 1));
if (i + 1 < rows && j - 1 >= 0)
if (matrix[i + 1, j - 1] == 1)
graph.AddAdjacent(i + "." + j, (i + 1) + "." + (j - 1));
}
}
}
// starting the depth first search
graph.Dfs(0);
}
}Connected Cells in a Grid Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'connectedCell' function below.
*
* The function is expected to return an INTEGER.
* The function accepts 2D_INTEGER_ARRAY matrix as parameter.
*/
public static int connectedCell(List<List<Integer>> matrix) {
// Write your code here
int max = 0, n = matrix.size(), m = matrix.get(0).size();
for(int i=0; i < n; i++){
for(int j=0; j < m; j++){
if(matrix.get(i).get(j)==1){
int temp[] = {0};
coverregion(matrix, i, j, n, m, temp);
max = Integer.max(max, temp[0]);
}
}
}
return max;
}
static void coverregion(List<List<Integer>>mt, int i,int j, int n, int m, int c[]){
if(i >= n || i < 0 || j >= m || j < 0)return;
if(mt.get(i).get(j) == 0)return;
mt.get(i).set(j, 0);
c[0]++;
coverregion(mt, i, j+1, n, m, c);
coverregion(mt, i, j-1, n, m, c);
coverregion(mt, i+1, j, n, m, c);
coverregion(mt, i-1, j, n, m, c);
coverregion(mt, i-1, j+1, n, m, c);
coverregion(mt, i+1, j+1, n, m, c);
coverregion(mt, i+1, j-1, n, m, c);
coverregion(mt, i-1, j-1, n, m, c);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int n = Integer.parseInt(bufferedReader.readLine().trim());
int m = Integer.parseInt(bufferedReader.readLine().trim());
List<List<Integer>> matrix = new ArrayList<>();
IntStream.range(0, n).forEach(i -> {
try {
matrix.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
int result = Result.connectedCell(matrix);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}Connected Cells in a Grid JavaScript Solution
function dfs(i,j,a,u){
//console.log(i+" "+j);
u[i][j]=1;
for(var ii=i-1;ii<=i+1;ii++)
for(var jj=j-1;jj<=j+1;jj++)
if(ii>=0 && jj>=0 && ii<a.length && jj<a[0].length && a[ii][jj] && !u[ii][jj])
dfs(ii,jj,a,u);
}
function processData(input) {
var data=input.split('\n');
var n=parseInt(data[0],10);
var m=parseInt(data[1],10);
var a=[];
for(var i=0;i<n;i++) {
a.push([]);
var arr=data[i+2].split(' ');
for(var j=0;j<m;j++)
a[i].push(arr[j].indexOf('1')!==-1?1:0);
//console.log(a[i]);
}
var u=[];
for(var i=0;i<n;i++){
u[i]=[];
for(var j=0;j<m;j++)
u[i][j]=0;
}
var ans=0;
var cur=0;
for(var i=0;i<n;i++)
for(var j=0;j<m;j++)
if(!u[i][j] && a[i][j])
{
var i1=i;
var j1=j;
dfs(i1,j1,a,u);
var next=0;
for(var k=0;k<n;k++)
for(var l=0;l<m;l++)
if(u[k][l]){
//console.log(k+" "+l);
next++;
}
ans=Math.max(next-cur,ans);
cur=next;
}
console.log(ans);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Connected Cells in a Grid Python Solution
import sys
number_of_rows = int(sys.stdin.readline())
number_of_columns = int(sys.stdin.readline())
grid = []
for row in range(number_of_rows):
row = sys.stdin.readline().strip('\s\n').split()
grid.append(row)
path_grid = [[set() for x in range(number_of_columns)] for x in range(number_of_rows)]
overall_max_area = int(0)
for current_row in range(number_of_rows):
for current_column in range(number_of_columns):
if (grid[current_row][current_column] != '0'):
max_path = set([(current_row, current_column)])
# Check for any connection from the row above
for last_column in range(current_column - 1, current_column + 2):
if (last_column >= 0 and last_column < number_of_columns):
max_path = max_path.union(path_grid[current_row - 1][last_column])
# Check for connection from the column on the left
if (current_column > 0 and len(path_grid[current_row][current_column - 1])):
max_path = max_path.union(path_grid[current_row][current_column - 1])
# Check for connection from row above that is not directly connected
for last_column in range(0, current_column - 1):
if (len(path_grid[current_row - 1][last_column])):
difference = path_grid[current_row - 1][last_column].difference(max_path)
if (len(difference) < len(path_grid[current_row - 1][last_column])):
max_path.update(difference)
for last_column in range(current_column + 2, number_of_columns):
if (len(path_grid[current_row - 1][last_column])):
difference = path_grid[current_row - 1][last_column].difference(max_path)
if (len(difference) < len(path_grid[current_row - 1][last_column])):
max_path.update(difference)
# Check for connection from the columns on the left that is not directly connected
for last_column in range(0, current_column - 1):
if (len(path_grid[current_row][last_column])):
difference = path_grid[current_row][last_column].difference(max_path)
if (len(difference) < len(path_grid[current_row][last_column])):
max_path.update(difference)
path_grid[current_row][current_column] = max_path
if (len(path_grid[current_row][current_column]) > overall_max_area):
overall_max_area = len(path_grid[current_row][current_column])
print(overall_max_area)
