Recursive Function to find regions in matrix

Question

Given a NxN matrix (which contains Boolean values - true / false). We will define:

• true region in an array as a maximum collection of adjacent cells that all have a true value.
• Cells located diagonally to each other are not considered adjacent.

In this example, there are 3 true areas: True Regions

My Solution attemp in Java:

public static int (boolean[][] mat) {
        return GetTrueRegions(mat, 0, 0);
    }
    public static int GetTrueRegions(boolean[][] m, int i , int j) {
        final boolean VISITED = false;
        if (i == m.length - 1 && j == m[0].length - 1)
            return 0;

        // avoid repeat a cell
        boolean temp = m[i][j];
        m[i][j] = VISITED;

        // recursion for all neighbors
        int up = -1, down = -1, left = -1, right = -1;
        if (i - 1 >= 0 && m[i-1][j] )
            up = GetTrueRegions(m, i - 1, j);
        if (i + 1 < m.length && m[i+1][j])
            down = GetTrueRegions(m, i + 1, j);
        if (j - 1 >= 0 && m[i][j-1])
            left = GetTrueRegions(m, i, j - 1);
        if (j + 1 < m[0].length && m[i][j+1] )
            right = GetTrueRegions(m, i, j + 1);
        // couldn't find a path
        if (temp) {
            return 1 + GetTrueRegions(m, i, j + 1);
        }
        if (up == -1 && down == -1 && left == -1 && right == -1 )
            return GetTrueRegions(m, i, j +1);

        return up + down + left + right;
    }

this obviously not working.

I was thinking about going through each cell, and if the cell has true value, adding 1 to the total regions(somehow), and put the value false to him and to each adjacent cell(mark the region as "visited").

though I find it hard for me to get the base cases, and how to get every region value.

Answer 1

try to look at something like that:

public static int GetTrueRegions(boolean[][] mat)
{
    return GetTrueRegions(mat, 0, 0);
}

private static int GetTrueRegions(boolean[][] m, int i, int j)
{
    if (j == m[0].length)
        return 0;       
        
    if (i == m.length)
        return GetTrueRegions(m, 0, j + 1);     

    // found a region 
    if (m[i][j])
    {
        // mark the entire region, to avoid duplications
        markRegionAsFalse(m, i, j);
        
        // count 1 region and proceed
        return 1 + GetTrueRegions(m, i + 1, j);
    }
    
    // proceed... 
    return GetTrueRegions(m, i + 1, j);
}

private static void markRegionAsFalse(boolean[][] matrix, int row, int col)
{
    // just visited...
    matrix[row][col] = false;
    
    if(row - 1 >= 0 && matrix[row - 1][col]) // move up and mark cell if true
        markRegionAsFalse(matrix, row - 1, col);
    
    if (row < matrix.length - 1 && matrix[row + 1][col]) // move down and mark cell if true
        markRegionAsFalse(matrix, row + 1, col);
    
    if (col < matrix.length - 1 && matrix[row][col + 1]) // move right and mark cell if true
        markRegionAsFalse(matrix, row, col + 1);
    
    if(col - 1 >= 0 && matrix[row][col - 1]) // move left and mark cell if true
        markRegionAsFalse(matrix, row, col - 1);            
}