Source Code
static int component(int[][] A, int x, int y) {
if(A != null && A[0] != null && 0 <= x && x < A.length && 0 <= y &&
y < A[0].length && A[x][y] == 1) {
A[x][y] = 2;
int up = component(A, x+1, y );
int down = component(A, x-1, y );
int right = component(A, x, y+1 );
int left = component(A, x, y-1 );
return right + left + down + up + 1;
}
return 0;
}
static int longest(int[][] A) {
int max = 0;
if(A != null) {
for(int i=0; i< A.length; i++) {
for(int j=0; j< A[0].length; j++) {
int count = component(A, i, j);
if(count > max)
max = count;
}
}
}
return max;
}
/*
Count the continuous connected components in 2d array
The problem can be viewed as four children tree, and count the longest path from the root
The data of node can be 0 or 1.
If data is 1 then travel to its children node,
else stop and return all the counts from children and add 1
*/
/*
[c-1, r]
[c, r-1] <- [c, r] -> [c, r+1]
[c+1, r]
*/
public static int count(int[][] arr, int c, int r){
int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0;
if(arr != null && arr.length > 0){
int height = arr.length;
int width = arr[0].length;
if(arr[c][r] == 1){
arr[c][r] = 0;
c1 = 1;
if(r + 1 < width){
c2 = count(arr, c, r+1);
}
if(r - 1 >= 0){
c3 = count(arr, c, r-1);
}
if(c + 1 < height){
c4 = count(arr, c+1, r);
}
if(c - 1 >= 0){
c5 = count(arr, c-1, r);
}
// arr[c][r] = 1;
}
}
return c5 + c1 + c2 + c3 + c4;
}
public static void test0(){
Aron.beg();
int[][] arr = {
{0, 0, 1, 0},
{1, 0, 1, 0},
{1, 0, 1, 1},
{1, 0, 0, 1}
};
int height = arr.length;
int width = arr[0].length;
int max = 0;
int count = 0;
for(int c=0; c max)
max = count;
}
}
Print.p("max=" + max);
Aron.end();
}