elrincondelc.com :: Ver tema - word-wrap en el codigo fuente

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

#define NUM_COLS 16
#define NUM_FILAS 16
#define MAX_NUM_CLUSTERS ((NUM_COLS * NUM_FILAS + 1) / 2)

/*
** Para cada objeto en la matriz se verifica la posible adyacencia con
** sus vecinos en la columna previa y/o fila previa. Esto se define en
** el programa como una pregunta: adyacencia? y la respuesta es:
*/
enum e_adyacencia {NINGUNA, IZQUIERDA_O_ARRIBA, IZQUIERDA_Y_ARRIBA};

void gen_matriz(int (*matriz)[NUM_COLS]);
void imp_matriz(int (*matriz)[NUM_COLS]);
int cont_clusters(int (*matriz)[NUM_COLS], int *cluster);

int main(void)
{
int matriz[NUM_FILAS][NUM_COLS];
int cluster[MAX_NUM_CLUSTERS + 1];
int i;

srand((unsigned) time(NULL));

gen_matriz(matriz);
imp_matriz(matriz);
puts("------------------------");

/* Calculo del numero de clusters (algoritmo Hoshen-Kopelman) */
cont_clusters(matriz, cluster);
imp_matriz(matriz);
puts("------------------------");

/* Estadistica: numero de clusters y cantidad de objetos de cada uno */
for (i = 1; i <= cluster[0]; i++)
printf("cluster[%02d] == %2d\n", i, cluster[i]);

return EXIT_SUCCESS;
}

/*
** Generacion de los objetos dentro de la matriz. Se asume que un valor
** distinto de cero indica un objeto mientras que el valor cero indica
** un espacio vacio.
*/
void gen_matriz(int (*matriz)[NUM_COLS])
{
int i, j;

for (i = 0; i < NUM_FILAS; i++)
for (j = 0; j < NUM_COLS; j++)
matriz[i][j] = rand() % 2;
}

/*
** Impresion de la matriz como una cuadricula
*/
void imp_matriz(int (*matriz)[NUM_COLS])
{
int i, j;

for (i = 0; i < NUM_FILAS; i++){
for (j = 0; j < NUM_COLS; j++)
if (matriz[i][j] != 0)
printf("%3d", matriz[i][j]);
else
printf(" ");

putchar('\n');
}
}

/*
** Implementacion del algoritmo Hoshen-Kopelman para el conteo del numero
** de clusters y numero de objetos en cada uno de estos. El algoritmo no
** esta optimizado y no se utiliza metodo alguno para acortar la ruta a
** seguir desde una etiqueta en particular hasta su etiqueta "padre".
**
** El valor de retorno de la funcion es el numero de clusters en la matriz,
** este valor tambien se almacena en cluster[0].
*/
int cont_clusters(int (*matriz)[NUM_COLS], int *cluster)
{
int etiqueta[MAX_NUM_CLUSTERS + 1];
int num_etiquetas;
int i, j;
int p, q;

/*
** Procesamiento de cada una de las celdas de la matriz, las
** celdas "vacias" (indicado por el valor cero) se ignoran.
*/
num_etiquetas = 0;
for (i = 0; i < NUM_FILAS; i++){
for (j = 0; j < NUM_COLS; j++){
if (!matriz[i][j])
continue;

/*
** Las variables "p" y "q" indican si existe un objeto adyacente
** en la fila previa y/o columna previa, respectivamente.
*/
p = i && matriz[i - 1][j];
q = j && matriz[i][j - 1];

switch (p + q){ /* Adyacencia? */
case NINGUNA:
matriz[i][j] = ++num_etiquetas;
etiqueta[matriz[i][j]] = 1;
break;
case IZQUIERDA_O_ARRIBA:
/*
** Ahora la variable "p" se utiliza para almacenar el "puntero"
** dado por la etiqueta de la fila (o columna) previa y obtener
** en base a esta su etiqueta "padre".
*/
p = matriz[i][j] = matriz[i - p][j - q];
while (etiqueta[p] < 0)
p = -etiqueta[p];
etiqueta[p]++;
break;
case IZQUIERDA_Y_ARRIBA:
/*
** Ahora la variables "p" y "q" se utilizan para almacenar los
** "punteros" dados por las etiquetas de la fila y columna
** previas y obtener en base a estas las etiquetas "padres".
*/
p = matriz[i - 1][j];
q = matriz[i][j - 1];
matriz[i][j] = p < q ? p : q;

while (etiqueta[p] < 0)
p = -etiqueta[p];
while (etiqueta[q] < 0)
q = -etiqueta[q];

/*
** Si las etiquetas indicadas por "p" y "q" son diferentes la
** etiqueta mayor se reasigna como un elemento "hijo" de la
** etiqueta menor.
*/
if (p < q){
etiqueta[p] += etiqueta[q] + 1;
etiqueta[q] = -p; /* "q" se reasigna como "hijo" de "p" */
}else if (p == q){
etiqueta[p]++;
}else /* p > q */ {
etiqueta[q] += etiqueta[p] + 1;
etiqueta[p] = -q; /* "p" se reasigna como "hijo" de "q" */
}
break;
}
}
}

/*
** Con este proceso se copia el numero de objetos por cluster a su
** ubicacion final (el array cluster[]) y se calcula el numero total
** de clusters almacenandose este valor en cluster[0].
**
** Tambien se copian las etiquetas "padre" a cada uno de sus "hijos",
** con esto se asegura que todos los objetos de un cluster utilizaran
** una sola etiqueta una vez re-etiquetados.
*/
etiqueta[0] = cluster[0] = 0;
for (i = 1; i <= num_etiquetas; i++)
if (etiqueta[i] > 0){
cluster[++cluster[0]] = etiqueta[i];
etiqueta[i] = cluster[0];
}else
etiqueta[i] = etiqueta[-etiqueta[i]];

/* Etiquetado final de todos los objetos de la matriz */
for (i = 0; i < NUM_COLS; i++)
for (j = 0; j < NUM_FILAS; j++)
matriz[i][j] = etiqueta[matriz[i][j]];

return cluster[0];
}