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:

  1. Assuma a posição como ponto de partida.
  2. 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).
  3. Escolha uma cor substituta e uma cor de destino.
  4. Viaje nas direções selecionadas.
  5. Se o bloco no qual você parar for da cor de destino, substitua a cor pela cor substituta.
  6. Repita os passos 4 e 5 até ter chegado a todos os lugares dentro dos limites.

Vamos pegar a matriz multidimensional abaixo como exemplo:

63b353b2864f97151e1319d0d4ff9866ce7822eb

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