Problema
Um livro de desafios mostra os três primeiros membros de uma família de padrões e pede o resto:
n = 1 n = 2 n = 3
A BBB CCCCC
BAB CBBBC
BBB CBABC
CBBBC
CCCCCObserve os desenhos antes de continuar lendo e tente descobrir a regra. Aqui está ela, de forma precisa: o membro n é um quadrado com 2n − 1 linhas, cada uma com 2n − 1 letras e sem espaços. Numere as linhas e as colunas a partir de 0 e considere o centro na posição n − 1. A casa na linha r e coluna c mostra a letra que vem d posições depois de A no alfabeto, onde d = max(|r − (n − 1)|, |c − (n − 1)|) é a quantidade de anéis que separam a casa do centro. Assim, o centro é A, o anel em volta dele é B, e a borda externa é a n-ésima letra.
Implemente decode_the_pattern(n).
Entrada
n: qual membro da família construir (no máximo 26, para que as letras nunca passem de Z).
Saída
Retorne as 2n − 1 linhas de cima para baixo. Quando n for 0, retorne uma lista vazia.
Restrições
0 ≤ n ≤ 26
Exemplos
Entrada:
n = 2
Saída esperada:
expected = ["BBB", "BAB", "BBB"]
Entrada:
long long n = 2;
Saída esperada:
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
Entrada:
long n = 2;
Saída esperada:
string[] expected = new string[] {"BBB", "BAB", "BBB"};
Explicação
Só o centro (1, 1) está a 0 anéis de distância; todas as outras casas estão a 1 anel: ["BBB", "BAB", "BBB"].
Entrada:
n = 4
Saída esperada:
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
Entrada:
long long n = 4;
Saída esperada:
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Entrada:
long n = 4;
Saída esperada:
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Explicação
As casas da borda estão a 3 anéis do centro (D); a linha 3 é a do meio: ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Marque o centro de cada quadrado de exemplo e veja como as letras mudam à medida que você se afasta dele.
Dica 2
Casas do mesmo anel têm a mesma letra; o número do anel é a maior entre as distâncias da linha e da coluna até o centro.
Dica 3
Confira a sua regra no exemplo n = 3 antes de construir qualquer n.
Complexidade esperada
tempo O(n^2), espaço extra O(n^2)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.