В сборнике головоломок показаны первые три члена семейства узоров, а остальные предлагается найти самостоятельно:
n = 1 n = 2 n = 3
A BBB CCCCC
BAB CBBBC
BBB CBABC
CBBBC
CCCCCПрежде чем читать дальше, внимательно рассмотрите их и попробуйте сформулировать правило. А вот и оно в точной форме: член с номером n представляет собой квадрат из 2n − 1 строк, в каждой из которых 2n − 1 букв без пробелов. Пронумеруем строки и столбцы с 0, тогда центр находится в позиции n − 1. В клетке в строке r и столбце c стоит буква, отстоящая в алфавите на d позиций от A, где d = max(|r − (n − 1)|, |c − (n − 1)|) показывает, на сколько колец клетка удалена от центра. Таким образом, в центре стоит A, в окружающем его кольце B, а на внешней границе n-я буква алфавита.
Реализуйте decode_the_pattern(n).
Входные данные
n: номер члена семейства, который нужно построить (не больше 26, чтобы буквы не вышли за Z).
Выходные данные
Верните 2n − 1 строк сверху вниз. Если n равно 0, верните пустой список.
Ограничения
0 ≤ n ≤ 26
Примеры
Ввод:
n = 2
Ожидаемый вывод:
expected = ["BBB", "BAB", "BBB"]
Ввод:
long long n = 2;
Ожидаемый вывод:
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
Ввод:
long n = 2;
Ожидаемый вывод:
string[] expected = new string[] {"BBB", "BAB", "BBB"};
Пояснение
Только центр (1, 1) удалён на 0 колец, все остальные клетки удалены на 1 кольцо: ["BBB", "BAB", "BBB"].
Ввод:
n = 4
Ожидаемый вывод:
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
Ввод:
long long n = 4;
Ожидаемый вывод:
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Ввод:
long n = 4;
Ожидаемый вывод:
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
Пояснение
Крайние клетки удалены на 3 кольца (D); строка 3 средняя: ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Отметьте центр каждого квадрата из примера и посмотрите, как меняются буквы при удалении от него.
Подсказка 2
У клеток одного кольца одна и та же буква; номер кольца равен большему из расстояний до центра по строке и по столбцу.
Подсказка 3
Прежде чем строить квадрат для любого n, проверьте своё правило на примере с n = 3.
Ожидаемая сложность
время O(n^2), доп. память O(n^2)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.