Предыдущие части: Подготовка, Первая реализация
Второй метод почти не отличается от первого, но на мой взгляд более изящен. Если ранее мы использовали 4 отдельных цикла для обхода периметра матрицы, а затем еще 4 цикла для внутренней части матрицы и т.д., то здесь у нас будет непрерывное движение по спирали в одном-единственном цикле от начала до конца.
Начнётся этот цикл точно так же: от первой клетки мы заполним строку числами по горизонтали, а дальше? А дальше мы продолжим этот же самый цикл, но поменяем направление движения.
Двигаться можно либо по горизонтали, либо по вертикали. Значит, следующий шаг определяется тем, какие направление заданы по x и по y. Назовём их dx и dy. Если dx = 1, то двигаемся вправо. Если dx = -1, то влево. Если dy = 1, то вниз, а если dy = -1, то вверх. Если dx и dy одновременно не нулевые, мы могли бы двигаться по диагонали, но нам это не нужно, поэтому в любом направлении будет активно только dx или только dy.
Создадим переменные-координаты x,y, а также переменные dx и dy, сразу назначив движение вправо:
x = 0
y = 0
dx = 1
dy = 0
Теперь сделаем единый цикл от 0 до N*N-1, который пройдёт по всем элементам матрицы:
Необычайно просто, не правда ли? Заполнили элемент матрицы – продвинулись дальше на dx и dy. Но пока что у нас проблема – двигаться мы будем только вправо, а необходимо менять направление в углах спирали.
Сначала напишем код для изменения направлений. Они должны меняться по часовой стрелке следующим образом:
1,0 → 0,1 → -1,0 → 0,-1 → 1,0
Мы могли бы использовать условия вроде
if dx == 1: dx = 0; dy = 1
elif dy == 1: dx = -1; dy = 0
elif ...
и так далее. Но примем во внимание, что изменение направления – это вращение вектора (dx,dy) на 90 градусов. И хотя формула вращения включает в себя тригонометрические функции, в нашем случае они вырождаются в 0 и 1 и приводят к простому правилу:
old_dx = dx
dx = -dy
dy = old_dx
А Питон, кроме того, позволяет обменять между собой значения двух переменных с помощью более короткой записи:
dx, dy = -dy, dx
Теперь нужно определить условия, при которых будет происходить поворот направления. Для внешнего периметра это просто: когда любая из текущих координат достигает нуля или N-1, нужно поворачивать.
А для внутреннего... это ещё проще. Так как внешний периметр уже заполнен, нам достаточно проверять, пустая клетка или нет. Если мы упираемся в заполненную клетку, то надо поворачивать.
Вот весь код (если не видно полностью, смотрите по ссылке):
Комментарии к коду:
В процессе движения по спирали только одна координата может выйти за пределы матрицы, но мы не знаем какая именно – x или y. Поэтому нужно писать проверку на обе:
if x < 0 or x == N or y < 0 or y < 0 or y == N ...
Из эстетических соображений я добавил переменную test. Если мы движемся по горизонтали, т.е. dx не равно нулю, тогда test соответствует следующему значению x, а иначе мы движемся по вертикали и тогда test соответствует следующему значению y.
Далее я проверяю только переменную test и содержимое следующей клетки матрицы a[y + dy][x + dx].
Моя реализация
Когда я решал эту задачу, то намеренно не смотрел чужие решения. Так совпало, что я выбрал именно такое решение, как описано здесь, но с некоторыми отличиями. Вместо двумерного массива я взял обычный одномерный список и двигался по нему, используя не координаты, а адрес (смещение от начала) ячейки. Я постоянно использую эту технику и вы можете найти её в следующих проектах:
Моменты, когда требуется повернуть, фиксированны: когда адрес равен N-1, равен N*N-1 или равен N*N-N, а дальше я просто начну упираться в непустые клетки.
Направление движения у меня теперь не пара dx,dy, а просто одно смещение, которое надо прибавить к адресу, чтобы переместить по горизонтали или по вертикали. Я уже не могу преобразовывать смещение по формуле поворота, поэтому просто сделал статичный список смещений:
dirs = (1, N, -1, N)
Обратите внимание на круглые скобки вместо квадратных: так в Питоне инициализируется статичный, то есть неизменяемый список.
Текущий номер смещения хранится в переменной dir, актуальное смещение получаем через dirs[dir], а циклическая смена номера получается через
dir = (dir + 1) & 3
Битовое "и" с числом 3 обеспечивает сброс номера в 0 на каждый четвертый раз.
Читайте также:
Финальный код:
Немного усложнился вывод на печать, но это не принципиально. Если делать красивый форматированный вывод, то его придётся переделывать во всех вариантах.
И наконец, спустя пару лет, я добавляю ещё одну свою реализацию, которая не требует матриц: