Backtracking, Programação Dinâmica e Flood Fill

Comparativo de Aplicações

Abaixo, uma tabela com exemplos clássicos do uso de Backtracking e Programação Dinâmica:

Quadro Comparativo: Aplicações de Algoritmos (fonte: chatGPT)

BacktrackingProgramação Dinâmica com MemoizationProgramação Dinâmica Tabular

Problema das 8 rainhasEncontrar todas as formas de colocar 8 rainhas em um tabuleiro 8x8 sem se atacaremO espaço de busca é grande, mas há muitas podas possíveisSudokuPreencher tabuleiro com regras de linhas, colunas e blocosO problema envolve tentativas sucessivas com regras rígidasGeração de labirintos ou quebra-cabeçasExploração de caminhos válidosÉ preciso explorar todas as possibilidades válidasPalavras cruzadas com dicionárioColocar palavras horizontal e verticalmente sem conflitoA exploração do estado exige validação progressivaSubconjuntos com soma-alvo (Subset Sum)Verificar se existe um subconjunto que soma a um valorA busca por todas as combinações possíveis é necessáriaResolver labirinto (caminho até a saída)Explorar caminhos até encontrar uma soluçãoPode não haver solução, e o algoritmo precisa tentar todas as opções

Flood Fill: O Problema

O Flood Fill é um algoritmo usado para preencher uma área contínua de uma matriz com uma nova cor, como a ferramenta de balde em editores de imagem. A partir de uma célula inicial, preenchermos todas as células conectadas com a mesma cor original.

Abordagens para Flood Fill

Várias estratégias podem ser utilizadas:

Comparativo de Estratégias para Flood Fill

DFS RecursivaChamada recursiva para cima, baixo, esquerda, direitaCódigo simples e elegantePode causar stack overflow em matrizes grandesDFS Iterativa (com pilha)Usa pilha manual para simular a recursãoEvita overflow de pilha, controle total da iteraçãoLevemente mais complexo que a versão recursivaBFS (com fila)Usa fila para expandir em 'largura', camada por camadaBoa para menor caminho em variantes do problemaPode consumir mais memóriaUnion-Find (Disjoint Set)Agrupa áreas conectadas em conjuntos e aplica a cor depoisÚtil quando há múltiplas queries de preenchimentoMais complexo de implementar e geralmente não vale a penaFlood Fill com Memoization (opcional)Evita visitar a mesma célula várias vezes se já foi processadaPode melhorar desempenho com cache inteligenteExige cuidado na estrutura de cache e pode ser redundante

Exemplo: FloodFill DFS recursivo

def flood_fill_dfs(imagem, x, y, cor_original, nova_cor):
    if x < 0 or x >= len(imagem) or y < 0 or y >= len(imagem[0]):
        return
    if imagem[x][y] != cor_original or imagem[x][y] == nova_cor:
        return

    imagem[x][y] = nova_cor

    # Visita as 4 direções: baixo, cima, direita, esquerda
    flood_fill_dfs(imagem, x + 1, y, cor_original, nova_cor)  # baixo
    flood_fill_dfs(imagem, x - 1, y, cor_original, nova_cor)  # cima
    flood_fill_dfs(imagem, x, y + 1, cor_original, nova_cor)  # direita
    flood_fill_dfs(imagem, x, y - 1, cor_original, nova_cor)  # esquerda

# 🌟 Exemplo de uso
imagem = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 1, 1, 1]
]

# Ponto inicial para preenchimento
x_inicial, y_inicial = 0, 0

# Cor original do ponto inicial
cor_alvo = imagem[x_inicial][y_inicial]

# Nova cor a ser preenchida
nova_cor = 9

# Aplica o algoritmo
flood_fill_dfs(imagem, x_inicial, y_inicial, cor_alvo, nova_cor)

# 📤 Resultado final
print("Imagem após Flood Fill (DFS Recursivo):")
for linha in imagem:
    print(linha)

Exemplo: FloodFill DFS iterativo com pilha

def flood_fill_dfs_iterativo(imagem, x, y, nova_cor):
    linhas = len(imagem)
    colunas = len(imagem[0])
    cor_original = imagem[x][y]

    if cor_original == nova_cor:
        return

    pilha = [(x, y)]

    while pilha:
        i, j = pilha.pop()

        if i < 0 or i >= linhas or j < 0 or j >= colunas:
            continue
        if imagem[i][j] != cor_original:
            continue

        imagem[i][j] = nova_cor

        # Adiciona os vizinhos à pilha (cima, baixo, esquerda, direita)
        pilha.append((i + 1, j))  # baixo
        pilha.append((i - 1, j))  # cima
        pilha.append((i, j + 1))  # direita
        pilha.append((i, j - 1))  # esquerda

# 🌟 Exemplo de uso
imagem = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 1, 1, 1]
]

# Ponto de partida
x_inicial, y_inicial = 0, 0
nova_cor = 9

# Aplicar Flood Fill
flood_fill_dfs_iterativo(imagem, x_inicial, y_inicial, nova_cor)

# 📤 Saída final
print("Imagem após Flood Fill (DFS Iterativo com Pilha):")
for linha in imagem:
    print(linha)

'''
Diferenciais:
Evita estouro de pilha em matrizes grandes (ao contrário da versão recursiva).

Pode ser facilmente adaptado para incluir mais direções (diagonais) ou restrições.
'''

Exemplo: BFS com Fila

from collections import deque
def flood_fill_bfs(matrix, x, y, target_color, new_color):
    if matrix[x][y] != target_color:
        return

    rows, cols = len(matrix), len(matrix[0])
    queue = deque([(x, y)])
    matrix[x][y] = new_color

    while queue:
        i, j = queue.popleft()
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            ni, nj = i + dx, j + dy
            if 0 <= ni < rows and 0 <= nj < cols and matrix[ni][nj] == target_color:
                matrix[ni][nj] = new_color
                queue.append((ni, nj))

Exemplo: FloodFill Union-Find (Disjoint Set)

class UnionFind:
    def __init__(self, linhas, colunas):
        self.parent = {}
        self.rank = {}
        self.linhas = linhas
        self.colunas = colunas
        for i in range(linhas):
            for j in range(colunas):
                self.parent[(i, j)] = (i, j)
                self.rank[(i, j)] = 0

    def find(self, pos):
        if self.parent[pos] != pos:
            self.parent[pos] = self.find(self.parent[pos])  # Path compression
        return self.parent[pos]

    def union(self, pos1, pos2):
        root1 = self.find(pos1)
        root2 = self.find(pos2)
        if root1 == root2:
            return
        if self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        else:
            self.parent[root2] = root1
            if self.rank[root1] == self.rank[root2]:
                self.rank[root1] += 1

def flood_fill_union_find(imagem, nova_cor, start_x, start_y):
    linhas = len(imagem)
    colunas = len(imagem[0])
    uf = UnionFind(linhas, colunas)
    cor_original = imagem[start_x][start_y]

    # União de regiões conectadas da mesma cor
    for i in range(linhas):
        for j in range(colunas):
            for dx, dy in [(1, 0), (0, 1)]:  # baixo e direita
                ni, nj = i + dx, j + dy
                if 0 <= ni < linhas and 0 <= nj < colunas:
                    if imagem[i][j] == imagem[ni][nj]:
                        uf.union((i, j), (ni, nj))

    # Encontrar a raiz da célula de origem
    origem_raiz = uf.find((start_x, start_y))

    # Pintar todas as células na mesma região conectada
    for i in range(linhas):
        for j in range(colunas):
            if uf.find((i, j)) == origem_raiz:
                imagem[i][j] = nova_cor

# 🌟 Exemplo de uso
imagem = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 1, 1, 1]
]

x_inicial, y_inicial = 0, 0
nova_cor = 9

flood_fill_union_find(imagem, nova_cor, x_inicial, y_inicial)

# 📤 Saída final
print("Imagem após Flood Fill (Union-Find):")
for linha in imagem:
    print(linha)

Exemplo: Flood Fill com DFS Recursivo e Memoization

def flood_fill_memo(image, x, y, new_color):
    rows, cols = len(image), len(image[0])
    original_color = image[x][y]

    if original_color == new_color:
        return image  # nada a fazer

    visited = set()

    def dfs(i, j):
        if (
            i < 0 or i >= rows or
            j < 0 or j >= cols or
            (i, j) in visited or
            image[i][j] != original_color
        ):
            return

        visited.add((i, j))
        image[i][j] = new_color

        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    dfs(x, y)
    return image
# 🌟 Exemplo de uso
imagem = [
    [1, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 1, 1, 1]
]

nova_cor = 9
x_inicial, y_inicial = 0, 0

resultado = flood_fill_memo(imagem, x_inicial, y_inicial, nova_cor)

print("Imagem após Flood Fill (Memoization):")
for linha in resultado:
    print(linha)

Quando usar cada um?

✅ DFS Recursivo: quando a área a ser preenchida é pequena ou moderada.

✅ DFS Iterativo: quando há risco de recursão profunda (ex: imagens muito grandes).

✅ BFS: quando a ordem de preenchimento importa (por exemplo, espalhamento em ondas).

✅ Union-Find: quando você precisa fazer vários preenchimentos independentes de forma eficiente.

⚠️ Memoization: raramente necessária para Flood Fill puro, mas útil se há sobreposição com outro problema (como segmentação de regiões).

Conclusão

O Flood Fill é um problema clássico e prático que pode ser resolvido de várias formas, cada uma adequada a contextos específicos. Ele também é uma excelente porta de entrada para entender a diferença entre DFS, BFS, uso de memória e controle de recursão. Já algoritmos como Backtracking e Programação Dinâmica são poderosas ferramentas para problemas combinatórios e de otimização, e sua aplicação adequada depende do tipo de problema que se deseja resolver.