Make delicious recipes!

Count blobs in a 2D matrix



Problem: Given a 2D matrix of booleans where true indicates white and false indicates black.
Considering group of adjacent black cells to be one blob, find the number of blobs in the matrix.

Example: Consider the below 6x5 matrix:

0 1 2 3 4
0                         
1                         
2                         
3                         
4                         
5                         

The solution function should output a count of 3 in the above case.

Solution:


Code:

// Pseudo code in java

int findBlobCount (int matrix[][], int rowCount, int colCount)
{
    int visited[][] = new int[rowCount][colCount]; // all initialized to false

    int count=0;
    for (int i=0; i<rowCount; i++)
    {
        for (int j=0; j<colCount; j++)
        {
            if (matrix[i][j] == false && visited[i][j] == false) // unvisited black cell
            {
                markVisited (i,j, matrix, visited, rowCount, colCount);
                count++;
            }
        }
    }

    return count;
}




int markVisited (int i, int j, int [][]matrix, int [][]visited, int rowCount, int colCount)
{
    if (i<0 || j<0)
        return;

    if (i>= rowCount || j>= colCount)
        return;

    if (visited[i][j] == true) // already visited
        return;

    if (matrix[i][j] == true) // not a black cell
        return;

    visited[i][j] = true;

    // recursively mark all the 4 adjacent cells - right, left, up and down
    markVisited (i+1, j, matrix, visited, rowCount, colCount);
    markVisited (i-1, j, matrix, visited, rowCount, colCount);
    markVisited (i, j+1, matrix, visited, rowCount, colCount);
    markVisited (i, j-1, matrix, visited, rowCount, colCount);
}









Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal