Preencher um grid em ordem espiral
A missão
Problema
Dados um número de linhas e um de colunas, construa um grid desse tamanho preenchido com os números de 1 a rows × cols em uma espiral no sentido horário, de fora para dentro: pela linha de cima para a direita, descendo pela coluna da direita, voltando pela linha de baixo, subindo pela coluna da esquerda e dando a volta de novo até que toda célula esteja preenchida. Retorne o grid como uma lista de linhas.
Exemplos
Input: rows = 3, cols = 3
Output: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
Por quê: a espiral termina na célula central
Input: rows = 3, cols = 4
Output: [[1, 2, 3, 4], [10, 11, 12, 5], [9, 8, 7, 6]]
Por quê: um grid largo termina em uma linha curta no meio, e não em uma única célula
Input: rows = 1, cols = 1
Output: [[1]]
Por quê: edge case: a espiral é um único passo
Dicas
0 / 3
Ande como uma tartaruga: guarde uma posição e uma direção, escreva o próximo número e dê um passo à frente.
As quatro direções em sentido horário são direita, baixo, esquerda e cima. Virar é passar para a próxima dessa lista.
Vire sempre que o próximo passo for sair do grid ou cair em uma célula já preenchida. Zero marca uma célula vazia, já que os números começam em 1.
- Tempo-alvo
- O(rows · cols)
- Espaço-alvo
- O(rows · cols)
Solução
Preencher uma espiral é a versão de leitura rodada ao contrário, e o jeito mais simples de escrevê-la é percorrer o grid passo a passo: guarde uma posição e uma direção, escreva o próximo número e vire no sentido horário sempre que o próximo passo for sair do grid ou bater em uma célula preenchida. As células preenchidas funcionam como o limite que encolhe, então não há quatro loops separados, um para cada borda, nem casos especiais para uma única linha ou coluna. Cada célula é escrita exatamente uma vez e cada passo faz trabalho constante, então o tempo é O(rows × cols) e o único espaço é o próprio grid.
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]]Travou na ideia, e não no código? Ordem espiral explica isso.