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 0 0 1 0 1 0 0 1 1 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行以便更好地理解）

0 0 0 0 1 0 1

在位置（1,5）处，您可以转到右上的1或右下的1（您的路径被一分为二），您将当前的L传递给这些路径中的每一个，然后，这些路径各自累加L，而不是累加全局L，全局L用于累加属于主路径的所有1，主路径的根是您找到的第一个1。

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

static int max;
static int L;

那么,每次启动一个新根1时,只需重新设置它的值,而不是通过您的方法传递L：

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

最后，在您的markVisited中，只需执行与您所做的相同的操作，但在您的方法末尾去掉那个L参数，因为您将使用全局参数：

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

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