(void *) blog

Posted on by fortytwo_de


... o el cubo de pintura de paint.exe.

Problema del concurso clasificatorio on-line 2 de OIE-2010. El PDF con el enunciado se puede descargar aquí.

El algoritmo que usaré para resolver el problema es el siguiente:

  • Si el punto P(x, y) está fuera del rango del tablero, se termina la función.
  • Si el color de una celda en la posición P(x, y) no es igual que el color objetivo, se termina la función.
  • Se establece el color de la celda en P(x, y) al color con el que se pinta.
  • Se hacen 4 llamadas recursivas a la función, en las direcciones norte, sur, este y oeste de P(x, y).

Implementación

Primero se definen unos tipos para mantener los valores organizados. Los que yo he usado son:

typedef struct {
    char** map;
    unsigned int sides;
} board_t;

typedef struct {
    unsigned int x;
    unsigned int y;
} point_t;

El primer tipo define el tablero, con el mapa de colores y la longitud de los lados. El segundo es un punto en dos dimensiones, con x e y.

Luego, unos métodos para inicializar los dos tipos (ya que se utilizarán como punteros y hay que asignar memoria).

point_t* init_point(void) {
    return (point_t*) malloc(sizeof(point_t));
}

board_t* init_board(int sides) {
    unsigned int y = 0;
    board_t* board = malloc(sizeof(board_t));

    board->map = malloc(sides * sizeof(char*));
    for(y = 0; y < sides; y++) {
        board->map[y] = malloc(sides * sizeof(char*));
    }
    board->sides = sides;

    return board;
}

El primero es simplemente una asignación de memoria con el tamaño de un puntero a point_t (qué meta). El segundo es algo más complicado porque tiene que inicializar una estructura para almacenar datos en dos dimensiones, pero tampoco es nada fuera de lo normal.

El siguiente paso es una función para mostrar el mapa de un tablero. La implementación es muy directa:

void print_map(board_t* board) {
    unsigned int x, y;

    for(y = 0; y < board->sides; y++) {
        for(x = 0; x < board->sides; x++) {
            printf("%c", board->map[x][y]);
        }
        printf("\n"); 
    }
}

Aquí se observa lo útil que es el tipo board_t, en vez de pasar la longitud de los lados como un argumento o tenerlo como variable global. Generalmente es una buena idea definir tipos de datos en vez de utilizar primitivos.

Para el algoritmo necesitamos unas funciones que calculen los puntos adyacentes al punto inicial. Con el tipo de datos point_t las funciones son muy sencillas:

point_t* north(point_t* origin) {
    point_t* result = init_point();
    result->x = origin->x;
    result->y = origin->y+1;

    return result;
}

point_t* south(point_t* origin) {
    point_t* result = init_point();
    result->x = origin->x;
    result->y = origin->y-1;

    return result;
}

point_t* east(point_t* origin) {
    point_t* result = init_point();
    result->x = origin->x+1;
    result->y = origin->y;

    return result;
}

point_t* west(point_t* origin) {
    point_t* result = init_point();
    result->x = origin->x-1;
    result->y = origin->y;

    return result;
}

No tiene ningún misterio, cada función modifica origin y devuelve un puntero a la nueva posición.

Y ahora viene la parte interesante, la implementación del algoritmo del pintor:

void fill(board_t* board, char target, char brush, point_t* coords) {
    if(coords->x < 0 || coords->x > board->sides-1 || coords->y < 0 || coords->y > board->sides-1) return; // out of bounds
    if(board->map[coords->x][coords->y] != target) return;
    board->map[coords->x][coords->y] = brush;

    fill(board, target, brush, north(coords));
    fill(board, target, brush, south(coords));
    fill(board, target, brush, east(coords));
    fill(board, target, brush, west(coords));
}

Creo que el código es muy legible: la primera línea comprueba si el punto está dentro de los límites del tablero (se resta 1 a la longitud de los lados porque los arrays en C, como en la mayoría de lenguajes, empiezan en el índice 0). El segundo comprueba si la celda del mapa de colores es el color objetivo, y si no lo es, se termina la función.

Luego se establece el color del mapa en ese punto, y se hacen llamadas recursivas a la función de llenado.

Un ejemplo gráfico del funcionamiento de este algoritmo:

Limitaciones

La limitación más prominente es el uso implícito del stack, ya que se hacen llamadas recursivas a cuya dirección de memoria hay que volver una vez terminado el algoritmo, y esto puede ocasionar problemas en entornos con un espacio de stack limitado.

Show me the code

El código completo se puede ver en pastie.

Notas

Sí, soy consciente de que al utilizar tipos de datos personalizados como punteros estoy pidiendo memory leaks. Pero bueno.

Posted on by fortytwo_de | Posted in Algoritmos, C, Programación


4 Responses to Flood fill, o “el algoritmo del pintor”

  1. Dirbaio says:


    Hola! :D

    En la linea que dice
    board_t* board = malloc(sizeof(board_t*));;

    no debería ser
    board_t* board = malloc(sizeof(board_t));;

    Porque si no, estas pidiendo memoria para el tamaño de un puntero a board_t, no del tamaño de board_t…


    • fortytwo_de says:


      @Dirbaio:

      Pues sí, tienes razón. Estaría pensando en la función init_map (para la cual sí necesito hacer malloc(sizeof(char*))) y me he colado.

      Y ya de paso, esa línea debería tener un solo ;. :P


  2. Gasti sixty MODAFOKIN nine says:


    Escuchame, el lugar donde dejaste el código está más caído que teta de vieja.

    Por favor, ponelo de nuevo en algúin lado.


Leave a Reply to pepe Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>