java递归函数在矩阵中寻找区域

nszi6y05 于 2021-06-27 发布在 Java

关注(0)|答案(1)|浏览(319)

给予 NxN 矩阵（包含布尔值-真/假）。我们将定义：
数组中所有具有真值的相邻单元格的最大集合。
位于对角线上的单元不被认为是相邻的。
在本例中，有3个真实区域：真实区域
我的解决方案尝试使用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（不知何故），然后将值设为假，并将其放入每个相邻的单元格中（将区域标记为“已访问”）。
虽然我发现我很难得到基本情况，以及如何得到每个地区的价值。

Java Algorithm recursion computer-science backtracking

来源：https://stackoverflow.com/questions/65566958/recursive-function-to-find-regions-in-matrix

1条答案

按热度按时间

vptzau2j1#

试着这样看：

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

赞(0）回复(0）举报 2021-06-27

我来回答

java递归函数在矩阵中寻找区域

1条答案

相关问题

热门标签

最新问答