Обход массива по улитке
Однажды мне на глаза попалась задачка, которую кому-то из хабравчан предложили для решения на собеседовании. Суть её состояла в том, чтобы заполнить квадратную матрицу с размерностью n*n числами от 1 до n^2 по спирали, закручивающейся от элемента [0, 0] к центру по часовой стрелке.
Поняв, что мысль о решении не дает мне покоя, я взялся вспоминать первый курс института. Минут 20 я рисовал квадратные матрицы разных размеров, пытаясь выявить закономерности, которые помогут упростить алгоритм обхода. Я выделил несколько интересных особенностей:
1.Каждый угловой элемент «улитки» (тот элемент, на котором происходит очередной поворот) можно легко рассчитать по формуле, зная размерность матрицы и номер шага:
C = l * s — M; l — размерность s — номер шага M — смещение
Смещение — это сдвиг от «края» матрицы. Ведь на каждой итерации угловые элементы приближаются к центру. Соответственно, он меняется с каждым шагом. Изначально он равен 0. Для следующего шага (s+1) он рассчитывается так:
M = M + delta; if(s % 2 != 0) delta = ceil(s / 2) s — номер шага
2.Зная угловой элемент и направление движения на следующем шаге, можно легко заполнить недостающие элементы.
Что ж, думаю, что этих вещей вполне достаточно для реализации задачи. На мой взгляд, главной изюминкой решения является идея с угловыми элементами. Мы сокращаем вычисления, сводя заполнение «неугловых» ячеек простым инкрементированием.
Я думаю, что в самой статье приводить листинг кода не нужно, а любой заинтересовавшийся может легко скачать код из репозитория.
Использование класса Snail очень простое. Мы создаём новый объект и вызываем у него метод cookSnail(int $length)
Текущая версия легко «готовит» и выводит «улитку» со стороной до 550 ячеек. Вот, собственно, и всё! Безошибочного вам кода!
