在矩阵中查找区域的递归函数

Question

给定一个NxN矩阵（包含布尔值-true/false）。我们将定义：

• 数组中的真实区域，作为所有具有真实值的相邻单元格的最大集合。
• 相互对角定位的单元格不被认为是相邻的。

在本例中，有3个真实区域：真实区域

我的解决方案在Java中尝试：

java prettyprint-override">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;
    }

这显然不起作用。

我在考虑遍历每个单元格，如果该单元格有真值，则在总区域（不知何故）中加1，然后将该值设为假，并将该值设为假（将该区域标记为“已访问”）。

虽然我发现很难获得基本情况，以及如何获得每个区域的值。

Answer 1

试着这样看：

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