Flood Fill

Q: Qual é a complexidade de tempo do Flood Fill?

O(m × n) para uma imagem com m linhas e n colunas. Cada pixel da região é colocado na pilha uma vez e verifica quatro vizinhos, e os pixels fora da região são apenas verificados como vizinhos. A pilha pode conter até m × n pixels quando a imagem inteira é uma única região.

Q: Você deve usar BFS ou DFS para o preenchimento por inundação?

Ambos funcionam e levam tempo O(m × n). A região é a mesma, independentemente da ordem em que você a percorre, então uma fila (busca em largura) e uma pilha (busca em profundidade) pintam os mesmos pixels. Escolha o que for mais curto de escrever na sua linguagem e evite recursão em imagens grandes.

Q: Por que o Flood Fill entra em um loop infinito quando a nova cor é igual à antiga?

A solução usual trata “ainda tem a cor antiga” como “ainda não foi visitado”. Quando a nova cor é igual à antiga, pintar um pixel não o altera, então seus vizinhos o colocam de volta na pilha e a busca nunca termina. Verificar esse caso primeiro e retornar a imagem corrige o problema, e a imagem inalterada é a resposta correta.

Q: Flood Fill pode ser resolvido recursivamente?

Sim, uma função que pinta um pixel e chama a si mesma em cada vizinho da cor antiga está correta. O risco está na profundidade: a recursão vai tão fundo quanto o caminho mais longo percorrido pela busca, que pode ter milhares de chamadas em uma região sinuosa. Uma pilha explícita faz o mesmo trabalho sem esse limite.

FácilGrafos

+10

Uma imagem é uma grade de números inteiros, em que cada número representa a cor de um pixel. Você recebe a imagem como uma lista de linhas, um pixel inicial na linha sr e na coluna sc, e uma nova color. Repinte a região que contém o pixel inicial: todos os pixels da cor do pixel inicial que você consegue alcançar a partir dele avançando para cima, para baixo, para a esquerda ou para a direita por pixels dessa mesma cor. Retorne a imagem após a repintura.

Função

floodFill(image: integer-2d-array, sr: integer, sc: integer, color: integer) → integer-2d-array

imageinteger-2d-array: a imagem como uma lista de linhas, um número por pixel
srinteger: a linha do pixel inicial, contada a partir de 0
scinteger: a coluna do pixel inicial, contada a partir de 0
colorinteger: a nova cor da região
Retornainteger-2d-array: a imagem após a região ser repintada

Restrições

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
Cada linha tem o mesmo comprimento.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length e 0 ≤ sc < image[0].length

Exemplos

Entrada: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
Saída: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
Explicação: O início contém a cor 1. O 1 à sua direita, os 1s na coluna da esquerda e ao longo da linha inferior, e o 1 acima do canto inferior direito estão todos conectados a ele, então os sete se tornam 5. Os dois 0s são de uma cor diferente e permanecem iguais.

+18 testes ocultos ao enviar

Para ir além

Como sua solução mudaria se os pixels que se tocam apenas pelos cantos também fossem considerados conectados?

Solução

A região é uma parte conexa de um grafo: os pixels são nós, e dois pixels da cor inicial que compartilham um lado estão conectados. Qualquer busca que comece no pixel indicado e percorra apenas pixels dessa cor encontra toda a região. As duas armadilhas são uma imagem em que a nova cor é igual à antiga e uma região longa e sinuosa que interrompe uma busca recursiva.

Busca em profundidade recursiva

Correta, mas não termina nos maiores testes

Intuição

Escreva uma função paint(r, c) que faz uma pequena coisa: se (r, c) estiver dentro da imagem e ainda tiver a cor antiga, atribua a nova cor e chame a si mesma nos quatro vizinhos. Uma chamada no pixel inicial se espalha por toda a região, porque cada pixel da região está ligado ao inicial por um caminho de pixels com a cor antiga, e as chamadas seguem esse caminho.

Pintar o pixel antes das quatro chamadas é o que impede que a propagação fique em círculos: quando um vizinho chama de volta um pixel já pintado, a cor não corresponde mais e a chamada retorna imediatamente. Isso só funciona quando a nova cor é diferente da antiga, então verifique isso primeiro e retorne a imagem sem alterações quando forem iguais.

O trabalho é O(m × n), mas a pilha de chamadas é o ponto fraco. A recursão chega à profundidade do caminho que está seguindo. Uma cobra de um pixel de largura passando por uma imagem de 80 × 80 tem cerca de 3.200 pixels de comprimento, então as chamadas ficam aninhadas em uma profundidade de cerca de 3.200. O Python para por padrão em 1.000 e gera um erro, e é por isso que essa abordagem não termina nos maiores testes. Outras linguagens permitem chamadas mais profundas, mas uma imagem maior também esgotaria a pilha de chamadas delas.

Algoritmo

Leia old = image[sr][sc]. Se old for igual a color, retorne a imagem.
Defina paint(r, c): retorne se (r, c) estiver fora da imagem ou se sua cor não for old.
Caso contrário, defina image[r][c] = color e chame paint nos pixels acima, abaixo, à esquerda e à direita.
Chame paint(sr, sc) e retorne a imagem.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])

    def paint(r, c):
        # Stop outside the image and at any pixel that is not the old color.
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = color
        paint(r + 1, c)
        paint(r - 1, c)
        paint(r, c + 1)
        paint(r, c - 1)

    paint(sr, sc)
    return image

Busca em profundidade com uma pilha explícita

Intuição

Faça o mesmo percurso, mas mantenha os pixels ainda a visitar numa pilha própria, em vez de na pilha de chamadas. Pinte o pixel inicial e empilhe-o. Desempilhe um pixel, examine seus quatro vizinhos e, para cada vizinho dentro da imagem que ainda tenha a cor antiga, pinte-o e empilhe-o. Quando a pilha estiver vazia, toda a região estará pintada.

Pinte um pixel quando o empilhar, não quando o desempilhar. Um pixel pintado já não tem a cor antiga, então a verificação da cor também funciona como verificação de visita: nenhum pixel entra na pilha duas vezes, e você não precisa de uma grade separada de marcações. Assim como na versão recursiva, a nova cor precisa ser diferente da antiga; portanto, retorne a imagem sem alterações quando elas forem iguais.

Cada pixel da região é empilhado uma vez e verifica quatro vizinhos, então o tempo é O(m × n). A pilha contém, no máximo, os pixels da região. Ela fica na memória comum, portanto uma região sinuosa de 3.200 pixels não é problema, ao contrário da versão recursiva, que esgotou a pilha de chamadas.

Algoritmo

Leia old = image[sr][sc]. Se old for igual a color, retorne a imagem.
Pinte (sr, sc) e coloque-o em uma pilha.
Retire um pixel da pilha e observe seus quatro vizinhos.
Para cada vizinho dentro da imagem cuja cor seja old, pinte-o e coloque-o na pilha.
Quando a pilha estiver vazia, retorne a imagem.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    # Painting a region its own color changes nothing. Returning here also
    # stops the search from pushing the same cells forever.
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
                # Paint on push: a painted cell no longer matches old,
                # so it can never be pushed twice.
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

Armadilhas e casos extremos

A maioria das respostas erradas se deve ao mesmo caso em que as cores são iguais, a sair dos limites da imagem ou à recursão em uma região grande.

Esquecer o caso em que color é igual à cor inicial. A pintura não altera nada, então uma busca que usa a cor como marca de pixels visitados empilha os mesmos pixels para sempre.
Ler image[sr][sc] depois de pintá-lo. Salve a cor antiga primeiro, ou você comparará cada vizinho com a nova cor.
Contar vizinhos diagonais. Pixels que se tocam apenas pelos cantos não estão conectados.
Verificar a cor de um vizinho antes de verificar se ele está dentro da imagem. Teste 0 ≤ row < rows e 0 ≤ col < cols primeiro.
Usar recursão em uma imagem grande. Um caminho com um pixel de largura em uma imagem de 80 × 80 tem cerca de 3.200 pixels de comprimento, profundidade suficiente para ultrapassar o limite de recursão do Python.
Pintar todos os pixels da cor antiga na imagem inteira. Pixels dessa cor que estão isolados do ponto inicial devem manter a cor.

Perguntas frequentes4

Qual é a complexidade de tempo do Flood Fill?

O(m × n) para uma imagem com m linhas e n colunas. Cada pixel da região é colocado na pilha uma vez e verifica quatro vizinhos, e os pixels fora da região são apenas verificados como vizinhos. A pilha pode conter até m × n pixels quando a imagem inteira é uma única região.

Você deve usar BFS ou DFS para o preenchimento por inundação?

Ambos funcionam e levam tempo O(m × n). A região é a mesma, independentemente da ordem em que você a percorre, então uma fila (busca em largura) e uma pilha (busca em profundidade) pintam os mesmos pixels. Escolha o que for mais curto de escrever na sua linguagem e evite recursão em imagens grandes.

Por que o Flood Fill entra em um loop infinito quando a nova cor é igual à antiga?

A solução usual trata “ainda tem a cor antiga” como “ainda não foi visitado”. Quando a nova cor é igual à antiga, pintar um pixel não o altera, então seus vizinhos o colocam de volta na pilha e a busca nunca termina. Verificar esse caso primeiro e retornar a imagem corrige o problema, e a imagem inalterada é a resposta correta.

Flood Fill pode ser resolvido recursivamente?

Sim, uma função que pinta um pixel e chama a si mesma em cada vizinho da cor antiga está correta. O risco está na profundidade: a recursão vai tão fundo quanto o caminho mais longo percorrido pela busca, que pode ter milhares de chamadas em uma região sinuosa. Uma pilha explícita faz o mesmo trabalho sem esse limite.

Python

def floodFill(image, sr, sc, color):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
sr = 0
sc = 0
color = 5

Esperado

[[5, 5, 0], [5, 0, 5], [5, 5, 5]]