Hackerrank Connected Cells in a Grid Solution

XXX
XYX  
XXX    

110
100
001

4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0

5

X X 0 0     1 1 0 0
0 X X 0     0 1 1 0
0 0 X 0     0 0 1 0
1 0 0 0     X 0 0 0

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

public class Solution {
    static int rs(int[][] matrix , int i , int j){
        if(i<0 || j<0 || i >= matrix.length || j >= matrix[i].length)
            return 0;
        if(matrix[i][j] == 0)
            return 0;
        int size = 1;
        matrix[i][j] = 0;
        for(int r = i-1; r<=i+1;r++){
            for(int c = j-1; c <= j+1; c++){
                if(r != i || c != j){
                    size += rs(matrix,r,c);
                }
            }
        }
        return size;
    }

    static int connectedCell(int[][] matrix,int n , int m ) {
        int max = 0;
        for(int i  = 0 ;i<n;i++){
            for(int j = 0 ;j<m;j++){
                if(matrix[i][j] == 1){
                    int size = rs(matrix , i ,j);
                    max = Math.max(size , max);
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] matrix = new int[n][m];
        for(int matrix_i = 0; matrix_i < n; matrix_i++){
            for(int matrix_j = 0; matrix_j < m; matrix_j++){
                matrix[matrix_i][matrix_j] = in.nextInt();
            }
        }
        int result = connectedCell(matrix,n,m);
        System.out.println(result);
        in.close();
    }
}

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

public class Solution {
    
    
    private static int countCells(int[][] matrix, int i, int j) {
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) return 0;
        if (matrix[i][j] == 0) return 0;
        int count = matrix[i][j]--;
        count += countCells(matrix, i + 1, j);
        count += countCells(matrix, i - 1, j);
        count += countCells(matrix, i, j + 1);
        count += countCells(matrix, i, j - 1);
        count += countCells(matrix, i + 1, j + 1);
        count += countCells(matrix, i - 1, j - 1);
        count += countCells(matrix, i - 1, j + 1);
        count += countCells(matrix, i + 1, j - 1);
        return count;
    }
    
    public static int getBiggestRegion(int[][] matrix) {
         int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                max = Math.max(max, countCells(matrix, i, j));
            }
        }
        return max;
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int grid[][] = new int[n][m];
        for(int grid_i=0; grid_i < n; grid_i++){
            for(int grid_j=0; grid_j < m; grid_j++){
                grid[grid_i][grid_j] = in.nextInt();
            }
        }
        System.out.println(getBiggestRegion(grid));
    }
}

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

public class Solution {

    static int[][] neighbours(int i, int j){
        return new int[][]{
            {i,j+1},{i,j-1},
            {i+1,j},{i+1,j+1},{i+1, j-1},  
            {i-1,j},{i-1,j-1},{i-1, j-1}
        };
    }
    
    static int newRegion(int[][] matrix, int i, int j){
        if(matrix[i][j] != 1)
            return 0;
        int n = matrix.length, m = matrix[0].length, counter = 0;
        List<int[]> cells = new ArrayList<int[]>();
        cells.add(new int[]{i, j});
        
        while(cells.size() > 0){
            int[] coords = cells.remove(0);
            i = coords[0];
            j = coords[1];
            if(i >= 0 && i < n && j >= 0 && j < m && matrix[i][j] == 1){
                matrix[i][j] = 2;
                int[][] neigh = neighbours(i, j);
                cells.addAll(Arrays.asList(neigh));
                ++counter;
            }
        } 
        
        return counter;
    }
    
    static int connectedCell(int[][] matrix) {
        int max_region = 0;
        for(int i = 0; i < matrix.length; ++i)
            for(int j = 0; j < matrix[0].length; ++j)
                max_region = Math.max(max_region, newRegion(matrix, i, j));
        
        return max_region;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] matrix = new int[n][m];
        for(int matrix_i = 0; matrix_i < n; matrix_i++){
            for(int matrix_j = 0; matrix_j < m; matrix_j++){
                matrix[matrix_i][matrix_j] = in.nextInt();
            }
        }
        int result = connectedCell(matrix);
        System.out.println(result);
        in.close();
    }
}

n=int(input())
m=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
def check(i,j):
    if i<0 or j<0 or i>=n or j>=m or l[i][j]==-1 or l[i][j]==0:
        return 0
    else:
        l[i][j]=-1
        return 1+(check(i,j+1)+check(i,j-1)+check(i+1,j)+check(i-1,j+1)+check(i-1,j-1)+check(i,j+1)+check(i+1,j-1)+check(i+1,j+1))

res= -1
for i in range(n):
    for j in range(m):
        if l[i][j]==1:
            res=max(res,check(i,j))
print(res)

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the connectedCell function below.
def connectedCell(matrix):
    mx = 0
    filled = [(i, j) for i, row in enumerate(matrix) for j,n in enumerate(row) if n]
    while filled:
        region = [filled.pop()]
        count = 0
        while region:
            n = region.pop()
            count += 1
            for f in list(filled):
                if abs(n[0] - f[0]) <= 1 and abs(n[1]-f[1]) <= 1:
                    region.append(f)
                    filled.remove(f)
        else:
            mx = max(mx, count)
    return mx

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    m = int(input())

    matrix = []

    for _ in range(n):
        matrix.append(list(map(int, input().rstrip().split())))

    result = connectedCell(matrix)

    fptr.write(str(result) + '\n')

    fptr.close()

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the connectedCell function below.

def dfs(matix, i, j, m, n, size):
    matrix[i][j] = 0
    dis = [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (1, 1), (-1, 1), (1, -1)]
    for di in dis:
        n_i = i + di[0]
        n_j = j + di[1]
        if 0 <= n_i < m and 0 <= n_j < n and matrix[n_i][n_j] == 1:
            size = dfs(matrix, n_i, n_j, m, n, size+1)
    return size

def connectedCell(matrix):
    m = len(matrix)
    n = len(matrix[0])
    max_size = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                size = dfs(matrix, i, j, m, n, 1)
                max_size = max(size, max_size)
    return max_size

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    m = int(input())

    matrix = []

    for _ in range(n):
        matrix.append(list(map(int, input().rstrip().split())))

    result = connectedCell(matrix)

    fptr.write(str(result) + '\n')

    fptr.close()

#include <bits/stdc++.h>
using namespace std;
struct _ { _() { cin.sync_with_stdio(0), cin.tie(0); } }_;

int arr[11][11];
int m = 0, n = 0;

int ff(int i, int j) {
    
    if (i < 0 || i >= m || j < 0 || j >= n 
        || arr[i][j] == -1 || arr[i][j] == 1)
        return 0;
    else {
        arr[i][j] = 1;
        return 1 + ff(i+1, j) + ff(i-1, j) + 
               ff(i, j+1) + ff(i, j-1) + 
               ff(i+1, j-1) + ff(i-1, j+1) + 
               ff(i+1, j+1) + ff(i-1, j-1);
    }
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int x; cin >> x;
            arr[i][j] = x-1; 
            // -1 = 0s, 0 = unvisited 1s, 1 = visited 1s
        }
    }
    int mx = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (arr[i][j] == 0)
                mx = max(mx, ff(i, j));
        }
    }
    cout << mx;
    return 0;
}

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int quant[100] = {0};

void pinta(int a[12][12], int x, int y, int atual)
{
    a[x][y] = atual;
    quant[atual]++;
    
    for (int i = x-1; i <= x+1; i++) {
        for (int j = y-1; j <= y+1; j++) {
            if ((i != x or j != y) and a[i][j] == 1)
                pinta(a, i, j, atual);
        }
    }
}

int main()
{
    int m, n;
    cin >> m >> n;
    
    int a[12][12] = {0};
    int atual = 2;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 1) {
                pinta(a, i, j, atual);
                atual++;
            }
        }
    }

    int maximo = 0;
    for (int i = 0; i < 100; i++) {
        if (quant[i] > maximo) maximo = quant[i];
    }
    printf("%d\n", maximo);
    
    return 0;
}