Algoritmos para cubo de pintura

Iniciado por juancho77, 3 Diciembre 2008, 15:05 PM

0 Miembros y 1 Visitante están viendo este tema.

juancho77

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:

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

ghastlyX

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