Repintar uma região conectada
A missão
Problema
Um grid de números representa as cores de uma imagem. Dados uma célula inicial e uma nova cor, repinte a célula inicial e toda célula alcançável a partir dela por passos para cima, para baixo, para a esquerda ou para a direita que passem só por células da cor original da célula inicial. Retorne o grid.
Exemplos
Input: grid = [[1, 1, 1],
[1, 1, 0],
[1, 0, 1]], row = 1, col = 1, colour = 2
Output: [[2, 2, 2],
[2, 2, 0],
[2, 0, 1]]
Por quê: o 1 do canto inferior direito só toca a região na diagonal, então ele fica como está
Input: grid = [[5]], row = 0, col = 0, colour = 3
Output: [[3]]
Input: grid = [[0, 0],
[0, 0]], row = 0, col = 0, colour = 0
Output: [[0, 0],
[0, 0]]
Por quê: edge case: repintar com a mesma cor não muda nada
Dicas
0 / 3
A região é definida pela conectividade, então o trabalho é um percurso que se expande a partir da célula inicial, e não uma varredura do grid inteiro.
Você precisa de um jeito de não visitar uma célula duas vezes. Pintar uma célula com a nova cor já a marca, desde que a nova cor seja diferente da antiga.
Guarde a cor original e retorne na hora se ela for igual à nova. Caso contrário, empilhe a célula inicial. Desempilhe uma célula; se ela estiver dentro do grid e ainda tiver a cor original, pinte-a e empilhe os seus quatro vizinhos. Pare quando a pilha estiver vazia.
- Tempo-alvo
- O(rows · cols)
- Espaço-alvo
- O(rows · cols)
Solução
Isto é um flood fill simples em profundidade a partir do início, em que a própria tinta serve de marca de visitado: assim que uma célula tem a nova cor, ela não corresponde mais à original e não será expandida de novo. Esse truque só funciona quando as duas cores são diferentes, e é por isso que cores iguais retornam cedo; sem essa verificação, as mesmas células seriam empilhadas para sempre. Uma pilha explícita evita que regiões profundas esgotem a pilha de chamadas (call stack). Cada célula da região é pintada uma vez e empilha quatro vizinhos, então o tempo é O(rows * cols) e a pilha é O(rows * cols) no pior caso.
def repaint(grid, row, col, colour):
old = grid[row][col]
if old == colour:
return grid # nothing to do, and no endless loop
stack = [(row, col)]
while stack:
r, c = stack.pop()
if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == old:
grid[r][c] = colour # painting doubles as the visited mark
stack += [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
return grid
print(repaint([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2)) # -> [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
print(repaint([[5]], 0, 0, 3)) # -> [[3]]
print(repaint([[0, 0], [0, 0]], 0, 0, 0)) # -> [[0, 0], [0, 0]]Travou na ideia, e não no código? Flood Fill explica isso.