I am having a 2D array of `land=0` and `water=1`. I have made a logic to get the maximum available land i.e maximum contiguous land bits available in the 2D array. However, when I use that logic on paper it is giving correct answer but on system it is not giving correct answer.

Say array `Array[3][9]` is having elements :

``0 1 1 0 1 0 0 0 10 1 0 1 0 0 0 0 01 1 1 1 1 0 0 1 1``

In the below code Array is input2.

The output should be 10.

The logic which I have developed is

``int countContigious(char* array[],int x,int y,int row1,int col1){if(x<0||x>=row1||y<0||y>=col1||array[x][y]!=0){return 0;}else{array[x][y]=2;return 1+countContigious(array,x-1,y,row1,col1)+countContigious(array,x+1,y,row1,col1)+countContigious(array,x,y-1,row1,col1)+countContigious(array,x,y+1,row1,col1);}}int largestSize(int input1[],char* input2[]){int row,col,i,j;int count=0;int result=0;row=input1[0];col=input1[1];for(i=0;i<row;i++){for(j=0;j<col;j++){if(input2[i][j]==0){count=countContigious(input2,i,j,row,col);if(count>result){result=count;}}}}return result;}``

According to me it should return answer in variable result. Can anyone tell what is wrong in my logic?

You have a 2D array. The usual way to traverse it, is be double for loop. The usual order will be this: 1st row - 1st column 1st row - 2nd column .. 1st row - last column 2nd row - 1st column ... last row - last column

Assume you are using the order described above, you may want to do something like this:

Every time you find a land bit, explore the array at the right, upper, right-upper, right-bottom and at the bottom of this position (the other directions are visited before this step) and find the max length of contigius zeros.

Here is very naive example:

``````#include <stdio.h>

int main() {
const int N = 4;
const int M = 5;

int a[4][5] =
{
{ 1, 0, 0, 0, 0},
{ 0, 0, 1, 1, 0},
{ 0, 1, 0, 0, 0},
{ 0, 0, 0, 0, 0}
};

/* A naive implementation, which can optimized.
* Some initializations are not needed.
*/

int i, j, k, z, len;
int max_len = -1;

// traverse the array in the order described before
for(i = 0 ; i < N ; ++i)
{
for(j = 0 ; j < M ; ++j)
{
/* Land bit found! Explore the array in the needed directions. */
if(a[i][j] == 0) {

// remember where we start from
k = i;
z = j;
len = 0;
// search right
// while we are inside the limits of the array
// (here we need to check only the columns, since
// we move to the right)
while(z < M) {
// and we find land bits
if(a[k][z++] == 0)
len++; // increase the current length
else     // we want contiguous land bits
break; // we found a water bit, so break this loop
}

// is the current length better than the current found?
if(len > max_len)
max_len = len; // yes, so update max_len

// return back to initial cell we started from
k = i;
z = j;
len = 0;
// search down
while(k < N) {
if(a[k++][z] == 0)
len++;
else
break;
}
if(len > max_len)
max_len = len;

k = i;
z = j;
len = 0;
// search right and down
while(k < N && z < M) {
if(a[k++][z++] == 0)
len++;
else
break;
}
if(len > max_len)
max_len = len;

k = i;
z = j;
len = 0;
// search upper
while(k >= 0) {
if(a[k--][z] == 0)
len++;
else
break;
}
if(len > max_len)
max_len = len;

k = i;
z = j;
len = 0;
// search upper and right
while(k >= 0 && z < M) {
if(a[k++][z++] == 0)
len++;
else
break;
}
if(len > max_len)
max_len = len;
}
}
}

printf("max_length = %d\n", max_len);

return 0;
}
``````

After understanding the naive approach, try to see where your approach misses. Use a paper and try with smaller examples. This site is not just for debugging. :)

[EDIT]

As Floris mentioned, this example assumes that the land is a straight line, in any direction.

Based on the answer of Floris, in order to get it work for the U shaped land, you need to modify your `countC` like this:

``````else
{
input2[x][y]=2;
return 1+countC(input2,x-1,y,r1,c1)+
countC(input2,x+1,y,r1,c1)+
countC(input2,x,y-1,r1,c1)+
countC(input2,x,y+1,r1,c1)+
countC(input2,x+1,y+1,r1,c1)+
countC(input2,x+1,y-1,r1,c1)+
countC(input2,x-1,y+1,r1,c1)+
countC(input2,x-1,y-1,r1,c1);
}
``````

as you can see, you would need to go into diagonals too.

Your code as written can be part of a working program - in other words, your logic is correct. I suspect that your problem is in "the code you didn't show". To demonstrate, I have taken your code and turned it into a complete working program - without changing your code at all.

Note though that you are doing something potentially dangerous where you write

``````if(x<0||x>=r1||y<0||y>=c1||input2[x][y]!=0)
``````

Since the compiler "short circuits" the OR statement, you never evaluation `input2[x][y]` when either of the indices are out of bounds - but I don't think that is behavior you ought to count on. It would be safer to test for boundaries first, and return `0` for "out of bounds"; then test for non-zero value for the location (which is now a "valid" location) in a separate `if` statement.

``````#include <stdio.h>
#include <stdlib.h>

int countC(char* input2[],int x,int y,int r1,int c1)
{

if(x<0||x>=r1||y<0||y>=c1||input2[x][y]!=0) // <<<< dangerous! better have two ifs >>>>
{
return 0;
}
else
{
input2[x][y]=2;
return 1+countC(input2,x-1,y,r1,c1)+countC(input2,x+1,y,r1,c1)+countC(input2,x,y-1,r1,c1)+countC(input2,x,y+1,r1,c1);
}
}
int largestSize(int input1[],char* input2[])
{
int r,c,i,j;
int count=0;
int result=0;
r=input1[0];
c=input1[1];
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(input2[i][j]==0)
{
count=countC(input2,i,j,r,c);
if(count>result)
{
result=count;
}
}
}
}
return result;
}

// <<< new function added to create a "variable size 2D array"
char **twoDchar(int rc, int cc) {
char** p;
int ii;
p = malloc(rc * sizeof (char*));
p[0]=malloc(rc * cc * sizeof(char));
for(ii=1; ii<rc; ii++) {
p[ii]=p[0]+ii*cc*sizeof(char);
}
return p;
}

// <<< added main() function to test the code >>>

int main(void) {
int dims[]={3,9};
char land[3][9]={ \
{0, 1, 1, 0, 1, 0, 0, 0, 1}, \
{0, 1, 0, 1, 0, 0, 0, 0, 0}, \
{1, 1, 1, 1, 1, 0, 0, 1, 1}};

char** lp;
int ii, jj;
lp = twoDchar(3,9);
for(ii=0;ii<3;ii++)
for(jj=0;jj<9;jj++) {
lp[ii][jj]=land[ii][jj];
}
printf("biggest mass is %d\n", largestSize(dims,lp));
}
``````

When I run the above, I do indeed get the answer `10`.

update for an example of "U shaped land":

``````  char land[3][9]={\
{0, 1, 1, 0, 1, 0, 1, 0, 1},\
{0, 1, 0, 1, 0, 0, 1, 0, 0},\
{1, 1, 1, 1, 1, 0, 0, 0, 1}};
``````

I get the answer `9` as expected.

note the comment I made when the question first appeared:

May I suggest that you include the code that creates your 2D "array" - since you actually create an array of arrays rather than a static 2D array. It's important to show how you did that - it might contain a bug, and it is needed for anyone to run your code.

Now that I took a closer look, it does appear like that might indeed have been the source of the problem (although you never did show how you came up with your 2D array).

Top