Repintar una región conexa
La misión
Problema
Una cuadrícula de números representa los colores de una imagen. Dada una celda inicial y un color nuevo, repinta la celda inicial y todas las celdas alcanzables desde ella con pasos hacia arriba, abajo, izquierda o derecha que pasen solo por celdas del color original de la celda inicial. Devuelve la cuadrícula.
Ejemplos
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é: el 1 de abajo a la derecha solo toca la región en diagonal, así que se queda igual
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é: caso límite: repintar con el mismo color no cambia nada
Pistas
0 / 3
La región se define por conectividad, así que el trabajo es un recorrido hacia afuera desde la celda inicial, no un barrido de toda la cuadrícula.
Necesitas una forma de no visitar una celda dos veces. Pintar una celda con el color nuevo ya la marca, siempre que el color nuevo sea distinto del viejo.
Recuerda el color original y devuelve la cuadrícula de inmediato si es igual al nuevo. Si no, apila la celda inicial. Saca una celda; si está dentro de la cuadrícula y todavía tiene el color original, píntala y apila sus cuatro vecinos. Detente cuando la pila quede vacía.
- Tiempo objetivo
- O(rows · cols)
- Espacio objetivo
- O(rows · cols)
Solución
Es un relleno en profundidad desde el inicio hacia afuera, donde la propia pintura sirve como marca de visitado: en cuanto una celda tiene el color nuevo, ya no coincide con el original y no se vuelve a expandir. Ese truco solo funciona cuando los dos colores son distintos, y por eso con colores iguales se devuelve antes; sin esa comprobación, las mismas celdas se apilarían para siempre. Una pila (stack) explícita evita que las regiones profundas agoten la pila de llamadas (call stack). Cada celda de la región se pinta una vez y apila cuatro vecinos, así que el tiempo es O(rows * cols) y la pila es O(rows * cols) en el peor 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]]¿Lo que te frena es la idea y no el código? Flood fill lo explica.