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

Question

Estoy trabajando en un proyecto en el que en un momento estoy estancado.

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 más larga adyacente de cualquier número contenido en la matriz.

Al igual que en la matriz por encima de la cadena más larga es de dígitos 2.

2 2 2 2 
    2 2 2 
    2 

Puede alguien me guíe en cuanto a lo que tengo que hacer para lograr este objetivo?

Gracias.

Answer 1

más fácil de dibujar que explicar ...

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

actualización:

Y ahora, con algo de código real:

#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

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 Breadth-First Search o Depth-First Search, obtendrá exactamente lo que desea. HTH

Answer 3

1. definir otra matriz 2d del mismo tamaño, inicialice todas las celdas a 0
2. conjunto valmáx a 0
3. si el array ayudante está lleno de ir de 1 a 5, de lo contrario se encontró una celda con 0 y hacer:
   valor de 3.1 cambio de la célula a 1
   3.2 establecer un contador a 1
   3.3 cheque 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 contador ++ y vaya a 2.1 con nuevas coordenadas.
4. maxval = max (maxval, contador), ir a 3
5. maxval retorno

los pasos 3.1 a 3.3, debe aplicarse como una función recursiva que toma coordinar y ambas matrices como argumentos y devuelve 1 + la suma de los valores devueltos de las llamadas recursivas.

Answer 4

Puede tratar esto como una imagen en una aplicación de pintura. Realice un flood-fill en cada elemento de su matriz 2D (a menos que ya esté rellenado por otra cosa) y realice un seguimiento de cuántos píxeles ha rellenado en cada paso.

Si la matriz se declara como

int elements[5][5]; 

A continuación, introducir una segunda matriz, que le indican si usted llenó un elemento ya (si lo desea, utilice un tipo diferente como bool si de eso está bien en su programa C):

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

a continuación, escribir una función recursiva que realiza un relleno por inundación y devuelve el número de elementos que estaban llenos (estoy escribiendo esto desde la parte superior de la cabeza, no hay garantía alguna de que esta función funciona 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, itere sobre su conjunto e intente completarlo por completo. Realizar un seguimiento de la mayor variedad llenado:

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, largestArea debe contener el tamaño de la cadena más larga de elementos adyacentes.

Answer 5

Me encantan 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 tal función fuera del estante.

Por favor, perdónenme 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 de ETS y un constructor para Point se vuelve mucho más compacto