Artigo original: Flood Fill Algorithm Explained
O algoritmo de preenchimento por inundação (do inglês, flood fill) é usado principalmente para determinar uma área limitada conectada a um determinado nó em uma matriz multidimensional. É muito semelhante à ferramenta do balde em programas como o Microsoft Paint.
A implementação mais usada do algoritmo é uma função recursiva baseada em pilha (em inglês, stack), e é sobre isso que falaremos a seguir.
Como funciona?
O problema é bastante simples e sua solução, geralmente, segue os passos abaixo:
- Assuma a posição como ponto de partida.
- Decida se quer ir nas quatro direções (N, S, O, L) ou em 8 direções (N, S, O, L, NO, NE, SO, SE).
- Escolha uma cor substituta e uma cor de destino.
- Viaje nas direções selecionadas.
- Se o bloco no qual você parar for da cor de destino, substitua a cor pela cor substituta.
- Repita os passos 4 e 5 até ter chegado a todos os lugares dentro dos limites.
Vamos pegar a matriz multidimensional abaixo como exemplo:
O quadrado vermelho é o ponto de partida e os quadrados em cinza são os limites.
Para mais detalhes, veja um trecho do código que descreve a função:
int wall = -1;
void flood_fill(int pos_x, int pos_y, int target_color, int color)
{
if(a[pos_x][pos_y] == wall || a[pos_x][pos_y] == color) // se não houver um limite ou se eu já não estive lá
return; // volte
if(a[pos_x][pos_y] != target_color) // se não for da cor, volte
return;
a[pos_x][pos_y] = color; // marque o ponto de modo que eu saiba que passei por ele.
flood_fill(pos_x + 1, pos_y, color); //depois, posso ir para o sul
flood_fill(pos_x - 1, pos_y, color); // o norte
flood_fill(pos_x, pos_y + 1, color); // o leste
flood_fill(pos_x, pos_y - 1, color); // ou o oeste
return;
}
Como vemos acima, meu ponto de partida é (4,4). Depois de chamar a função para as coordenadas de início, x = 4 e y = 4, posso começar a conferir se há ou não um limite ou uma cor no local. Se for válido, marco o local com uma cor (color) e começo a verificar os quadrados adjacentes.
Indo para o sul, chegarei ao ponto (5,4) e a função é executada novamente.
Problema do exercício
Sempre considerei que resolver um ou mais problemas usando um algoritmo recém aprendido é a melhor maneira de entender o conceito por completo.
Aqui temos um problema:
Instrução: em uma matriz bidimensional, você recebe um número n fornecido de "ilhas". Tente achar a maior área de uma ilha e o número da ilha correspondente. 0 significa água e qualquer outro x entre 1 e n significa um quadrado da superfície correspondente à ilha x.
Entradas
- n – o número de ilhas.
- l, c – as dimensões da matriz.
- o próximo número, onde l é a linha e c é a coluna, dando a l-ésima linha da matriz.
Resultado
- i – o número da ilha com a maior área.
- A - a área da i-ésima ilha.
Exemplo:
Você tem a entrada abaixo:
2 4 4
0 0 0 1
0 0 1 1
0 0 0 2
2 2 2 2
Para qual delas você terá a ilha número 2 como sendo a maior área, com 5 quadrados.
Dicas
O problema é bem fácil, mas aqui você tem algumas dicas:
1. Use o algoritmo de preenchimento por inundação sempre que encontrar uma nova ilha.
2. Diferente do que ocorre no código de exemplo, você deve percorrer a ára da ilha, não a do oceano (blocos com 0).