问题描述:

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 1`

0 1 0 1 0 0 0 0 0

1 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).