Encontrar todos los elementos adyacentes en una matriz 2D en C

Estoy trabajando en un proyecto donde en un momento estoy atascado.

Mi pregunta es, por ejemplo, tengo la siguiente matriz 2D que contiene 3 enteros diferentes.

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 

Lo que quiero es encontrar la cadena de elementos adyacentes más larga de cualquier número contenido en la matriz.

Como en la matriz anterior, la cadena más larga es del dígito 2.

 2 2 2 2 2 2 2 2 

¿Puede alguien simplemente guiarme en cuanto a lo que tengo que hacer para lograr este objective?

Gracias.

Más fácil de dibujar que de explicar …

 2 2 2 2 1 => AAAAB => (A: 4, B: 1) 1 2 2 2 1 => CAAAB => (A: 3 + 4, B: 1 + 1, C: 1) 3 3 2 3 2 => DDAEF => (A: 1 + 7, B: 2, C: 1, D: 2, E: 1, F: 1) 3 1 3 3 1 => DGEEG => (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 => ... 

actualización :

Y ahora, con un código real:

 #include  #include  #include  #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); } 

Supongamos que su matriz es un gráfico, y los elementos son vértices. Dos vértices están conectados si son adyacentes y tienen el mismo valor. Si realiza cualquier búsqueda en ese gráfico, ya sea la Búsqueda en la amplitud o la Búsqueda en la Profundidad , obtendrá exactamente lo que desea. HTH

  1. define otra matriz 2d del mismo tamaño, inicializa todas las celdas a 0
  2. establece maxval a 0
  3. si la matriz de ayuda está llena de 1, vaya a 5, de lo contrario encuentre una celda con 0 y haga:
    3.1 cambiar el valor de la celda a 1
    3.2 poner un contador a 1
    3.3 verifique todas las celdas adyacentes, si son 0 en la matriz auxiliar y el mismo valor que la celda actual en la matriz de entrada, entonces contadores ++ y vaya a 2.1 con nuevas coordenadas.
  4. maxval = max (maxval, contador), vaya a 3
  5. volver maxval

los pasos 3.1-3.3 deben implementarse como una función recursiva que toma coordenadas y ambas matrices como argumentos y devuelve 1 + la sum de los valores devueltos de las llamadas recursivas.

Puedes tratar esto como una imagen en una aplicación de pintura. Realice un relleno por inundación en cada elemento de su matriz 2D (a menos que ya esté lleno por otra cosa) y haga un seguimiento de cuántos píxeles rellenó en cada paso.

Si su matriz se declara como

 int elements[5][5]; 

Luego introduzca una segunda matriz que indique si ya llenó un elemento (si lo desea, use un tipo diferente como bool si eso está bien en su progtwig C):

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

A continuación, escriba una función recursiva que realice un relleno de inundación y devuelva el número de elementos que se llenaron (estoy escribiendo esto desde la parte superior de mi cabeza, sin ninguna garantía de que esta función funcione como es):

 int floodFill( int x, int y ) { int filledPixels = 0; if ( !pixelFilled[x][y] ) { ++filledPixels; pixelFilled[x][y] = 1; } 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; } 

Finalmente, itera sobre tu matriz y trata de llenarla completamente. Mantenga un registro de la mayor matriz llena:

 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; } } } 

Ahora, la zona más largestArea debe contener el tamaño de la cadena más larga de elementos adyacentes.

Amo este tipo de problemas 🙂 así que aquí está mi respuesta. Como dijo Frerich Raabe, esto se puede resolver con una función floodFill. Por ejemplo, la biblioteca opencv proporcionaría una función de este tipo.

Por favor, perdóneme si en el siguiente código encontrará rastros de C ++, en caso de que sean fáciles de reemplazar.

 typedef struct Point { int x; int y; } Point; int areaOfBiggestContiguousRegion(int* mat,int nRows, int nCols) { int maxArea = 0; int currValue, queueSize, queueIndex; int* aux; Point queue[1000]; //Stores the points I need to label Point newPoint, currentPoint; int x,y,x2,y2; //Code: allocate support array aux of same size of mat //Code: fill aux of zeros for (y = 0; y < nRows; y++) for (x = 0; x < nCols; x++) if (aux[y * nCols + x] == 0) {//I find a pixel not yet labeled, my seed for the next flood fill queueIndex = 0; //Contains the index to the next element in the queue queueSize = 0; currValue = mat[y * nCols + x]; //The "color" of the current spot aux[y * nCols + x] = 1; newPoint.x = x; newPoint.y = y; queue[queueSize] = newPoint; queueSize++; while(queueIndex != queueSize) { currPoint = queue[queueIndex]; queueIndex++; //Look left, right, up, down x2 = currPoint.x - 1; y2 = currPoint.y; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (x2 >= 0 && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } x2 = currPoint.x + 1; y2 = currPoint.y; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (x2 < nCols && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } x2 = currPoint.x; y2 = currPoint.y - 1; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (y2 >= 0 && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } x2 = currPoint.x; y2 = currPoint.y + 1; //Some copy & paste, sorry I have been too long on C++ to remember correctly about C functions if (y2 < nRows && aux[y2 * nCols + x2] == 0 && mat[y2 * nCols + x2] == currValue) { aux[y2 * nCols + x2] = 1; newPoint.x = x2; newPoint.y = y2; queue[queueSize] = newPoint; queueSize++; } } //while if (queueSize > maxArea) maxArea = queueSize; //If necessary we could store other details like currentValue }//if (aux... return maxArea; } 

Nota: en C ++, utilizando contenedores estándar y un constructor para Point se vuelve mucho más compacto.