问题描述:

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

相关阅读:
Top