Llenar una cuadrícula en espiral
La misión
Problema
Dada una cantidad de filas y de columnas, construye una cuadrícula de ese tamaño llena con los números del 1 a rows × cols en una espiral hacia adentro en sentido horario: por la fila de arriba hacia la derecha, bajando por la columna derecha, de vuelta por la fila de abajo, subiendo por la columna izquierda, y otra vuelta más hasta llenar todas las celdas. Devuelve la cuadrícula como una lista de filas.
Ejemplos
Input: rows = 3, cols = 3
Output: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
Por qué: la espiral termina en la celda central
Input: rows = 3, cols = 4
Output: [[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]]
Por qué: una cuadrícula ancha termina en una fila central corta en lugar de en una sola celda
Input: rows = 1, cols = 1
Output: [[1]]
Por qué: caso límite: la espiral es un solo paso
Pistas
0 / 3
Avanza como una tortuga: lleva una posición y una dirección, escribe el siguiente número y da un paso adelante.
Las cuatro direcciones en sentido horario son derecha, abajo, izquierda y arriba. Girar es pasar a la siguiente de esa lista.
Gira cada vez que el siguiente paso fuera a salir de la cuadrícula o a caer en una celda ya llena. El cero marca una celda vacía, ya que los números empiezan en 1.
- Tiempo objetivo
- O(rows · cols)
- Espacio objetivo
- O(rows · cols)
Solución
Llenar una espiral es lo mismo que leerla, pero al revés, y la forma más simple de escribirlo es avanzar paso a paso: lleva una posición y una dirección, escribe el siguiente número y gira en sentido horario cada vez que el siguiente paso fuera a salir de la cuadrícula o a chocar con una celda llena. Las celdas llenas actúan como un borde que se va encogiendo, así que no hacen falta cuatro bucles separados, uno por borde, ni casos especiales para una sola fila o columna. Cada celda se escribe exactamente una vez y cada paso hace trabajo constante, así que el tiempo es O(rows × cols) y el único espacio es la propia cuadrícula.
def spiral_fill(rows, cols):
grid = [[0] * cols for _ in range(rows)] # 0 = not filled yet
moves = [(0, 1), (1, 0), (0, -1), (-1, 0)] # right, down, left, up
r = c = d = 0
for value in range(1, rows * cols + 1):
grid[r][c] = value
nr, nc = r + moves[d][0], c + moves[d][1]
if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc]:
d = (d + 1) % 4 # blocked: turn clockwise
nr, nc = r + moves[d][0], c + moves[d][1]
r, c = nr, nc
return grid
print(spiral_fill(3, 3)) # -> [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
print(spiral_fill(3, 4)) # -> [[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]]
print(spiral_fill(1, 1)) # -> [[1]]¿Lo que te frena es la idea y no el código? Orden en espiral lo explica.