Finding all adjacent elements in a 2D array

Question

I am working on a project where at one point I am stuck.

My question is for example I have the following 2D array containing 3 different integers.

2 2 2 2 1 
1 2 2 2 1 
3 3 2 3 2 
3 1 3 3 1 
1 1 2 3 1 
1 3 1 3 3 

What I want is to find the longest adjacent elements chain of array of any number contained in the array.

Like in the above array the longest chain is of digit 2.

2 2 2 2
  2 2 2
    2

Can anyone just guide me as to what I have to do to achieve this goal?

Answer 1

Easier to draw than to explain...

2 2 2 2 1 => A A A A B => (A: 4, B: 1)
1 2 2 2 1 => C A A A B => (A: 3 + 4, B: 1 + 1, C: 1)
3 3 2 3 2 => D D A E F => (A: 1 + 7, B: 2, C: 1, D: 2, E: 1, F: 1)
3 1 3 3 1 => D G E E G => (A: 8, B: 2, C: 1, D: 2 + 1, E: 2 + 1, F: 1, G: 1)
1 1 2 3 1 => ...
1 3 1 3 3 => ...

update:

And now, with some real code:

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

#define ROWS 6
#define COLS 5

unsigned char eles[ROWS][COLS] = { { 2, 2, 2, 2, 1 }, 
                                   { 1, 2, 2, 2, 1 }, 
                                   { 3, 3, 2, 3, 2 }, 
                                   { 3, 1, 3, 3, 1 }, 
                                   { 1, 1, 2, 3, 1 }, 
                                   { 1, 3, 1, 3, 3 } };

struct zone {
  int acu;
  int row, col;
  int refs;
};

typedef struct zone zone;

zone *
new_zone(int row, int col) {
  zone *z = (zone *)malloc(sizeof(zone));
  z->col = col;
  z->row = row;
  z->refs = 1;
  z->acu = 0;
}

void croak (const char *str) {
  fprintf(stderr, "error: %s\n", str);
  exit(1);
}

void
free_zone(zone *z) {
  if (z->refs != 0) croak("free_zone: reference count is not cero");
  free(z);
}

zone *
ref_zone(zone *z) {
  z->refs++;
  return z;
}

void
unref_zone(zone *z) {
  z->refs--;
  if (!z->refs) free_zone(z);
}

int
main() {
  zone *last[COLS];
  zone *current[COLS];
  zone *best = new_zone(0, 0);
  int i, j;
  memset(last, 0, sizeof(last));

  for (j = 0; j < ROWS; j++) {
    for (i = 0; i < COLS; i++) {
      unsigned int ele = eles[j][i];
      zone *z;
      /* printf("analyzing ele: %d at row %d, col: %d\n", ele, j, i); */
      if (i && (ele == eles[j][i-1])) {
        /* printf("  equal to left element\n"); */
        z = ref_zone(current[i-1]);
        if (j && (ele == eles[j-1][i])) {
          zone *z1 = last[i];
          /* printf("  equal to upper element\n"); */
          if (z != z1) {
            int k;
            /* printf("  collapsing zone %p\n", z1); */
            z->acu += z1->acu;
            for (k = 0; k < COLS; k++) {
              if (last[k] == z1) {
                last[k] = ref_zone(z);
                unref_zone(z1);
              }
            }
            for (k = 0; k < i; k++) {
              if (current[k] == z1) {
                current[k] = ref_zone(z);
                unref_zone(z1);
              }
            }
          }
        }
      }
      else if (j && (ele == eles[j-1][i])) {
        /* printf("  equal to upper element\n"); */
        z = ref_zone(last[i]);
      }
      else {
        /* printf("  new element\n"); */
        z = new_zone(j, i);
      }
      z->acu++;
      current[i] = z;
      /* printf("  element zone: %p\n", z); */
    }
    for (i = 0; i < COLS; i++) {
      if (j) unref_zone(last[i]);
      last[i] = current[i];
      if (best->acu < current[i]->acu) {
        unref_zone(best);
        best = ref_zone(current[i]);
        /* printf("best zone changed to %p at row; %d, col: %d, acu: %d\n", best, best->row, best->col, best->acu); */
      }
    }
  }
  printf("best zone is at row: %d, col: %d, ele: %d, size: %d\n", best->row, best->col, eles[best->row][best->col], best->acu);
}

Answer 2

Suppose your matrix is a graph, and the elements are vertices. Two vertices are connected if they are adjacent and have the same value. If you perform any search in that graph, be it Breadth-First Search or Depth-First Search, you'll get exactly what you want. HTH

Answer 3

You could treat this like a picture in a paint application. Perform a flood-fill on each element in your 2D array (unless its filled already by something else) and keep track how many pixels you filled in each step.

If your array is declared like

int elements[5][5];

Then introduce a second array which tells whether you filled an element already (if you like, use a different type like bool if thats's okay in your C program):

int pixelFilled[5][5];
memset( pixelFilled, 0, sizeof( pixelFilled ) );

Next, write a recursive function which performs a flood fill and returns the numbers of elements which were filled (I'm writing this from the top of my head, no guarantee whatsoever that this function works as it is):

int floodFill( int x, int y ) {
  int filledPixels = 0;
  if ( !pixelFilled[x][y] ) {
    ++filledPixels;
    pixelFilled[x][y] = 1;
  } else {
    return 0;
  }
  if ( x < 4 && elements[x+1][y] == elements[x][y] )
    filledPixels += floodFill( x + 1, y );
  if ( x > 0 && elements[x-1][y] == elements[x][y] )
    filledPixels += floodFill( x - 1, y );
  if ( y < 4  && elements[x][y+1] == elements[x][y] )
    filledPixels += floodFill( x, y + 1 );
  if ( y > 0  && elements[x][y-1] == elements[x][y] )
    filledPixels += floodFill( x, y - 1 );
  return filledPixels;
}

Finally, iterate over your array and try to fill it completely. Keep track of the largest filled array:

int thisArea = 0;
int largestArea = 0;
int x, y;
for ( y = 0; y < 5; ++y ) {
  for ( x = 0; x < 5; ++x ) {
    thisArea = floodFill( x, y );
    if (thisArea > largestArea ) {
      largestArea = thisArea;
    }
  }
}

Now, largestArea should contain the size of the longest chain of adjacent elements.