O algoritmo de flood fill calcula a área relacionada a uma dada posição de uma matriz.
Normalmente o algoritmo necessita da posição, de uma cor inicial e de uma cor substituto. O que o algoritmo faz é trocar a cor inicialpela cor substituto de todas as posições conectadas à posição inicial que tenham essa cor inicial.
Este gif animado (via wikipedia) mostra a ideia geral (assume-se conectadas posições na ortogonal e na diagonal):
O algoritmo seguinte utiliza a representação matricial da class Graph para implementar o flood fill. Isto significa que não se deve interpretar o objecto grafo usado no flood-fill como um grafo mas apenas como uma matriz 2D.
Existem dois valores para os vectores dr[ ] e dc[ ] que correspondem a ter conexões apenas ortogonais (o que está comentado) ou conexões ortogonais e diagonais. Dependendo do problema, devem escolher os valores adequados.
static int dr[] = {1,1,0,-1,-1,-1, 0, 1}; // trick to explore an implicit 2D grid
static int dc[] = {0,1,1, 1, 0,-1,-1,-1}; // S,SE,E,NE,N,NW,W,SW neighbors
//static int dr[] = {1,0,-1, 0}; //
//static int dc[] = {0,1, 0,-1}; // S,E,N,W neighbors
/**
* Use graph structure to simulate a 2D grid
* Replaces the old color by the new considering all directions,
* and returns the total number of replacements
* @ensures a total chaotic graph if interpreted by default
* @complexity O(V + E)
* @throws Exception If representation is non-sparce (ie, it needs the adjacency matrix)
*/
public int floodFill(int row, int col, int oldColor, int newColor) throws Exception {
if (isSparse)
throw new Exception("Flood Fill only works on a non-sparce representation");
if (row < 0 || row >= size || col < 0 || col >= size)
return 0; // outside grid
if (graphMatrix[row][col] != oldColor)
return 0; // does not have old color
graphMatrix[row][col] = newColor; // recolors vertex to avoid cycling
int ans = 1; // adds 1 because vertex (row, col) was replaced
for (int d = 0; d < 8; d++)
ans += floodFill(row + dr[d], col + dc[d], oldColor, newColor);
return ans; //
}
Neste exemplo, o algoritmo é recursivo. Poder-se-ia implementar uma versão iterativa com uma stack. Fica como exercício para os curiosos.
Experimentem o problema UVa 469 - Wetlands of Florida.
Outros problemas: