Connected Cells in a Grid Hackerrank problem solution

Connected Cells in a Grid Hackerrank

Consider a matrix with n rows and , columns, where each cell contains either a 0 or a 1 and 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 other words, cell c[i][j] is connected to cells [i-1][j-1], [i-1][j], [i-1][j+1], [i][j-1], [i][j+1], [i+1][j-1], [i+1][j], and [i+1][j+1], provided that the location exists in the matrix for that [i][j].

If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to at least one other cell in the region but is not necessarily directly connected to all the other cells in the region.

Task
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.

Input Format

The first line contains an integer, n, denoting the number of rows in the matrix.
The second line contains an integer, m, denoting the number of columns in the matrix.
Each line i of the n subsequent lines contains m space-separated integers describing the respective values filling each row in the matrix.

Constraints

0Output Format

Print the number of cells in the largest region in the given matrix.

Sample Input

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

Sample Output

5

Explanation

The diagram below depicts two regions of the matrix; for each region, the component cells forming the region are marked with an X:

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

The first region has five cells and the second region has one cell. Because we want to print the number of cells in the largest region of the matrix, we print 5.

Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT

dire = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

def dfs(i, j, mat, mark, color):
    if i < 0 or i >= len(mat) or j < 0 or j >= len(mat[0]): return
    if mat[i][j] == 0: return
    if mark[i][j] != -1: return
    mark[i][j] = color
    for d in dire:
        dfs(i+d[0], j+d[1], mat, mark, color)
        
N = int(raw_input())
M = int(raw_input())
mat = []
for i in xrange(N):
    mat.append(map(int, raw_input().split()))
mark = [ [-1]*M for i in xrange(N)]
c = 0
for i in xrange(N):
    for j in xrange(M):
        dfs(i, j, mat, mark, c)
        c += 1

count = [0]*(N*M)
for i in xrange(N):
    for j in xrange(M):
        if mark[i][j] != -1:
            count[mark[i][j]] += 1
            
print max(count)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
int n, m, x[MAXN][MAXN];


int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &x[i][j]);
        }
    }
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (x[i][j] == 0) continue;
            int cnt = 1;
            queue<vector<int> > q;
            q.push({i, j});
            x[i][j] = 0;
            while (!q.empty()) {
                vector<int> front = q.front();
                q.pop();
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = -1; dy <= 1; dy++) {
                        int nx = dx + front[0];
                        int ny = dy + front[1];
                        if (nx >= 0 && ny >= 0 && nx < n && ny < m && x[nx][ny] == 1) {
                            x[nx][ny] = 0;
                            cnt++;
                            q.push({nx, ny});
                        }
                    }
                }
            }
            maxi = max(maxi, cnt);
        }
    }
    printf("%d\n", maxi);
    return 0;
}
function fill(arr, i, j, m, n) {
    // return if any of the indices is out of matrix bounds
    if (i < 0 || i >= m || j < 0 || j >= n) 
        return 0;
    else if (arr[i][j] == 1) {
    	// zero the element for a "visited"-like indicator,
        // so every connected component is recursed through
        // only once 
        arr[i][j] = 0;
        // return 1 as the component size, adding the recursive
        // returns for all its possible neighbours
        return 1+fill(arr, i-1, j-1, m, n)
                +fill(arr, i-1, j, m, n)
                +fill(arr, i-1, j+1, m, n)
                +fill(arr, i, j-1, m, n)
                +fill(arr, i, j+1, m, n)
                +fill(arr, i+1, j-1, m, n)
                +fill(arr, i+1, j, m, n)
                +fill(arr, i+1, j+1, m, n);
    }
    return 0;
}
function processData(input) {
    // read and parse the input
    var arr = input.split(/\r?\n/);
    var m = arr[0], n = arr[1], chck = 0, rslt = 0;
    arr = arr.slice(2).map(e => e.split(' ').map(Number));
    // cycle through every element of the matrix
    for (var i = 0; i < m; i++) {
        for (var j = 0; j < n; j++) {
            // check arr[i][j] value and count its component
            chck = fill(arr, i, j, m, n);
            // compare this component size with max size yet
            rslt = (chck > rslt) ? chck : rslt;
        }
    }
    console.log(rslt);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.