Imprimir Página - Algoritmos para cubo de pintura

A ver quien se las ingenia mejor. Propongo sugieran algoritmos (si en vez de un algoritmo ponen un codigo, vale, pero bien comentado, asi todos nos entendemos) para simular la funcion cubo de pintura de los paintbrush (MS PAINT, KolourPaint, etc). El cubo de pintura (para los que no sepan :¬¬) rellena el menor area encerrada que sea del mismo color al punto donde hemos hecho click con el raton.

Dejo el mio para empezar:

Código:

//inicio
pintarPuntos (pixel p)
 crear un arreglo con todos los puntos circundantes (los que lo rodean)
 repetir desde x=0 hasta x=longitud del arreglo
  si el elemento pixel x del arreglo es del mismo color que el punto inicial
    pintar x.
    pintarPuntos(formar nuevo arreglo con los puntos circundantes de arreglo(x))
  sino
   pasar al siguiente punto
//fin

Como es recursivo, creo que comeria un monton, pero me parece que funcionaria correctamente.

Esto suele resolverse con un BFS o DFS. Tu tienes en una matriz de enteros donde el valor de la posicion matriz[ i][j] corresponde al píxel que ocupa dicha posición. Llamas a la función indicando la posición del píxel inicio, la matriz y el nuevo color. Una vez en la función, la mecánica es guardarse el color antiguo del píxel, cambiarlo y luego comprobar los vecinos, ya sea recursivamente (DFS, tipo lo que has hecho) o iterativamente mediante una cola (BFS). Por ejemplo, este problema de la UVa se resuelve así:
http://icpcres.ecs.baylor.edu/onlinejudge/external/5/572.html

Un saludo de ghastlyX ;)

Foro de elhacker.net

Programación => Ejercicios => Mensaje iniciado por: juancho77 en 3 Diciembre 2008, 15:05 pm