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

Question

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

真实区域 在数组中作为 相邻单元格 的最大集合，它们都具有真实值。
彼此成对角线的单元格不被视为相邻。

在这个例子中，有3个真实区域： True Regions

我在 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;
    }

这显然行不通。

我正在考虑遍历每个单元格，如果单元格具有真值，则将总区域加 1（以某种方式），并将值 false 给他和每个相邻单元格（将区域标记为“访问过”）。

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

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

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

Recursive Function to find regions in matrix

java

algorithm

recursion

computer-science

backtracking