Unit Area of largest region of 1's

Question

Consider a matrix with N rows and M columns, where each cell contains either a ‘0’ or a ‘1’ and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. If one or more filled cells are connected, they form a region. The task is to find the unit area of the largest region.

Here is my code:

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

    }
}

The code is not working for below mentioned test case:
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
output is 13, expected is 14.
Interestingly, If I change x_pos and y_pos (commented in code) in markVisited method as

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

output is 14. I don't understand how output can change when the x_pos and y_pos combinations are same.
Its happening for other test cases also. I have commented x_pos[] and y_pos[].
Please suggest what's wrong.

Answer 1

So, your issue is the way you accumulate L recursively. Here is your input array:

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

Just as an example. If the path you have already accumulated is splitted in two different paths (let's pick up the first 3 rows of your input for better understanding)

1 1 1 1 0 0 1

1 0 1 0 1 1 0

0 0 0 0 1 0 1

At position (1, 5), you can go either to the 1 at the top right, or the 1 at the bottom right (your path is divided in two), you are passing the current L to each of those and then, each of those paths are accumulating L on their own, instead of accumulating a global L which is intended to accumulate all the 1's found that belongs to the main path whose root is the first 1 you found.

Your fix is really simple, just move L to the top of your variables, like this:

static int max;
static int L;

Then instead of passing L through your methods, just reset its value back each time you start a new root 1:

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

And finally, in your markVisited, just do the same thing you do but getting rid of that L param at the end of your method, since you are going to use the global one:

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

Hope that helps, let me know if it is not clear so I can add more details if needed ^-^

It worth to mention that the fact that your code works well if you change the variables is a coincidence because this behavior depends on the way you go through the 1's in your iteration. Depending on which 1 you choose first, you can either fall in this case or not, so changing them is not the solution.

Answer 2

The problem is with the way you're accumulating the count of visited cells.

Firstly you need to change your outer loop to:

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

Then your markVisited method should return the count of cells visited, so change the signature to:

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

Finally you need to accumulate the count as you recurse into the neighbors of a cell:

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;

With these changes you get the desired output, regardless of the order in which you visit neighbors:

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