[Solved] How to find contigious elements in a 2D array using C

Question

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.

Accepted Answer