Задачу спирального заполнения матрицы я уже описывал в этой подборке:
Там есть три решения, но все они используют массив. Нет ничего плохого в использовании массива, но это приводит к следующим ограничениям:
- Если матрица большая, она может не поместиться в памяти
- Чтобы вывести матрицу на экран, надо сначала заполнить её целиком. Нет возможности выводить построчно прямо в процессе вычислений.
- Чтобы узнать, какое число записано в произвольной клетке матрицы, её надо также сначала заполнить целиком (или как минимум до этой клетки)
Можно ли написать простой цикл, который построчно выводит числа из матрицы, не прибегая к самой матрице, то есть вычисляя каждое число на лету?
Да, у меня постоянно было ощущение, что сделать это можно, но конкретная реализация ускользала. Потому что движение по спирали порождает целую кучу противоречивых условий.
В конце концов удалось сесть и формализовать задачу через набор постулатов, и вот что у меня получилось:
Матрица состоит из вложенных друг в друга периметров. Если размер матрицы N*N, то её внешний периметр состоит из N клеток вправо, N-1 клеток вниз, N-1 клеток влево и N-2 клеток вверх:
Формула длины периметра это N * 4 - 4.
Я решил сосредоточиться только на периметре и придумать метод для трансляции любых координат (x, y) внутри матрицы на какую-то клетку этого периметра.
Координаты попадают на периметр, когда x = 0, или x = N-1, или y = 0, или y = N-1. В остальных случаях я пока просто ничего не делаю.
Далее получается довольно просто:
- Если y = 0, значит мы находимся в первом плече периметра, и адрес клетки будет равен x.
- Если x = N-1, значит мы находимся во втором плече периметра, и адрес клетки будет равен N (длина первого плеча) + N-1-y.
- Если y = N-1, значит мы находимся в третьем плече периметра, и адрес будет равен N + (N-1) * 2 - x
и т.д.
Я возможно не совсем точно пишу формулы, но тут важен сам принцип, а формулы я поправил в финальном коде.
Т.е. зная, в каком плече периметра мы находимся, и размер каждого плеча, мы можем вычислить смещение клетки от начала периметра.
Таким образом, для любого заданного периметра с размером N*N уже можно вычислить адрес клетки.
Что тогда делать с координатами, которые не попадают в периметр?
Как я написал выше, матрица состоит из вложенных друг в друга периметров. Стало быть, если координаты клетки не принадлежат внешнему периметру, тогда они принадлежат одному из внутренних. А это уже легко проверить, если заменить внешний периметр на следующий внутренний и сделать проверку координат ещё раз.
При переходе на внутренний периметр я делаю три коррекции:
- к результирующему адресу клетки прибавляется сумма длин предыдущих периметров
- от координат (x, y) отнимается 1, так как начало координат у внутреннего периметра больше на 1
- N уменьшается на 2, это новый размер внутреннего периметра
Если во внутреннем периметре также не найдена клетка, лежащая на нём, то происходит переход на следующий внутренний периметр аналогичным образом.
Данный алгоритм оформлен в виде рекурсивной функции, которая или возвращает адрес клетки, или вызывает сама себя, передавая данные для внутреннего периметра.
Код на PHP:
Вот такой результат печатается на экране (линии пририсовал я):
Следующий вопрос – можно ли это всё написать не с помощью условий, а с помощью какой-то мега-формулы? Кажется, что да, но на это у меня уже точно не хватит мозгов :)