1的最大区域的单位面积

Question

考虑一个具有 N 行和 M 列的矩阵，其中每个单元格包含“0”或“1”，任何包含 1 的单元格都称为填充单元格。如果两个单元格在水平、垂直或对角线上相邻，则称它们已连接。如果连接一个或多个填充单元格，它们将形成一个区域。任务是求最大区域的单位面积

这是我的代码：

class GFG {
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            max = 1;
            int R = sc.nextInt();
            int C = sc.nextInt();
            int[][] M = new int[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    M[i][j] = sc.nextInt();
                }
            }
            printMatrix(M, R, C);
            boolean[][] visited = new boolean[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    int L = 1;
                    if (M[i][j] == 1 && !visited[i][j])
                        markVisited(M, visited, i, j, R, C, L);
                }
            }
            System.out.println(max);
        }
    }

    private static void printMatrix(int[][] M, int R, int C) {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                System.out.print(M[i][j] + " ");
            }
            System.out.println();
        }

    }

    public static boolean isSafe(int[][] M, boolean[][] visited, int i, int j, int R, int C) {
        return ((i >= 0 && i < R) && (j >= 0 && j < C) && (M[i][j] == 1 && (!visited[i][j])));
    }

    public static void markVisited(int[][] M, boolean[][] visited, int x, int y, int R, int C, int L) {
        // int[] x_pos = {1 , 1, 1, 0, 0, -1, -1, -1};
        // int[] y_pos = {-1, 0, 1, -1, 1, -1, 0, 1};
        //commenting the arrays, as selecting one of the above and below combinations, result in different outputs
        int[] x_pos = { -1, -1, -1, 0, 0, 1, 1, 1 };
        int[] y_pos = { -1, 0, 1, -1, 1, -1, 0, 1 };

        visited[x][y] = true;
        for (int k = 0; k < 8; k++) {
            if (isSafe(M, visited, x + x_pos[k], y + y_pos[k], R, C)) {
                L++;
                max = Math.max(L, max);
                markVisited(M, visited, x + x_pos[k], y + y_pos[k], R, C, L);
            }
        }

    }
}

代码不适用于下面提到的测试用例：
1
4 7
1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1
输出为 13，预期为 14。
有趣的是，如果我将 markVisited 方法中的 x_pos 和 y_pos （在代码中注释）更改为

int[] x_pos = {1 , 1, 1, 0, 0, -1, -1, -1};  
int[] y_pos = {-1, 0, 1, -1, 1, -1, 0, 1};

输出为 14。我不明白当 x_pos 和 y_pos 组合相同时输出如何变化。
它也发生在其他测试用例中。我评论了 x_pos[] 和 y_pos[].
有什么问题请指教

Answer 1

所以，你的问题是递归累加 L 的方式。这是您的输入数组：

1 1 1 1 0 0 1

1 0 1 0 1 1 0

0 0 0 0 1 0 1

1 0 0 0 1 1 1

举个例子。如果您已经积累的路径被分成两个不同的路径（让我们拿起您输入的前 3 行以便更好地理解）

1 1 1 1 0 0 1

1 0 1 0 1 1 0

0 0 0 0 1 0 1

在位置(1, 5)，你可以走到右上角的1，也可以走到右下角的1（你的路径一分为二），你把当前的L传递给每一个然后，这些路径中的每一个都在自己累积 L，而不是累积全局 L，后者旨在累积所有发现的属于主路径的 1，其根是您找到的第一个 1。

您的修复非常简单，只需将 L 移动到变量的顶部，如下所示：

static int max;
static int L;

然后，不要通过您的方法传递 L，只需在每次启动新根 1 时重置其值即可：

if (M[i][j] == 1 && !visited[i][j]) {
    L = 1;
    markVisited(M, visited, i, j, R, C);
}

最后，在你的 markVisited 中，做同样的事情，但在你的方法结束时去掉那个 L 参数，因为你将使用全局参数：

max = Math.max(++L, max);

希望对您有所帮助，如果不清楚请告诉我，以便我在需要时添加更多详细信息^-^

值得一提的是，如果您更改变量，您的代码运行良好这一事实纯属巧合，因为这种行为取决于您在迭代中处理 1 的方式。取决于你先选择哪一个，这种情况你要么跌倒，要么不跌倒，所以改变它们不是解决办法。

Answer 2

问题出在您计算已访问单元格计数的方式上。

首先，您需要将外循环更改为：

int max = 0;          
for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
        if (M[i][j] == 1 && !visited[i][j])
          max = Math.max(max, markVisited(M, visited, i, j, R, C));
    }
}
System.out.println(max);

然后你的 markVisited 方法应该 return 访问的单元格计数，所以将签名更改为：

public static int markVisited(int[][] M, boolean[][] visited, int x, int y, int R, int C)

最后，您需要在递归到单元格的相邻单元格时累加计数：

int L = 1;
for (int k = 0; k < 8; k++) {
    if (isSafe(M, visited, x + x_pos[k], y + y_pos[k], R, C)) {           
        L += markVisited(M, visited, x + x_pos[k], y + y_pos[k], R, C);
    }
}
return L;

通过这些更改，无论您访问邻居的顺序如何，您都可以获得所需的输出：

1 1 1 1 0 0 1 
1 0 1 0 1 1 0 
0 0 0 0 1 0 1 
1 0 0 0 1 1 1 
14

1的最大区域的单位面积

Unit Area of largest region of 1's

java

algorithm

graph

breadth-first-search

depth-first-search