HackerRank Connected Cells in a Grid 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;
}

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

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);
        }
}

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();
    }
}

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);
});

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)