El relleno por inundación es un algoritmo que se utiliza principalmente para determinar un área delimitada conectada a un nodo dado en una matriz multidimensional. Se parece mucho a la herramienta de cubo en los programas de pintura.
La implementación más abordada del algoritmo es una función recursiva basada en pila, y de eso es de lo que hablaremos a continuación.
¿Como funciona?
El problema es bastante simple y generalmente sigue estos pasos:
- Toma la posición del punto de partida.
- Decida si quiere ir en 4 direcciones ( N, S, W, E ) u 8 direcciones ( N, S, W, E, NW, NE, SW, SE ).
- Elija un color de reemplazo y un color de destino.
- Viaja en esas direcciones.
- Si la ficha en la que aterrizas es un objetivo, reemplázala con el color elegido.
- Repita 4 y 5 hasta que haya estado en todas partes dentro de los límites.
Tomemos la siguiente matriz como ejemplo:
El cuadrado rojo es el punto de partida y los cuadrados grises son las llamadas paredes.
Para obtener más detalles, aquí hay un fragmento de código que describe la función:
int wall = -1; void flood_fill(int pos_x, int pos_y, int target_color, int color) Como se vio arriba, mi punto de partida es (4,4). Después de llamar a la función para las coordenadas de inicio x = 4 e y = 4 , puedo comenzar a verificar si no hay pared o color en el lugar. Si eso es válido, marco el lugar con un "color" y comienzo a comprobar los otros cuadrados adyacentes.
Yendo hacia el sur llegaremos al punto (5,4) y la función vuelve a ejecutarse.
Problema de ejercicio
Siempre consideré que resolver uno (o más) problemas utilizando un algoritmo recién aprendido es la mejor manera de comprender completamente el concepto.
Así que aquí tienes uno:
Declaración:
En una matriz bidimensional se le da n número de "islas" . Trate de encontrar el área más grande de una isla y el número de isla correspondiente. 0 marca agua y cualquier otra x entre 1 y n marca un cuadrado de la superficie correspondiente a la isla x.
Entrada
- n - el número de islas.
- l, c - las dimensiones de la matriz.
- las siguientes l líneas, c números que dan la l- ésima fila de la matriz.
Salida
- i - el número de la isla con el área más grande.
- A - el área de la i 'ésima isla.
Ex:
Tienes la siguiente entrada:
2 4 4 0 0 0 1 0 0 1 1 0 0 0 2 2 2 2 2Por lo que obtendrás la isla no. 2 como la isla más grande con el área de 5 cuadrados.
Sugerencias
El problema es bastante fácil, pero aquí hay algunas sugerencias:
1. Use the flood-fill algorithm whenever you encounter a new island. 2. As opposed to the sample code, you should go through the area of the island and not on the ocean (0 tiles).