Добрый день.
Сегодня хочу представить методы обхода ячеек в двухмерной прямоугольной сетке.
К каждому методу прикреплен графический пример. Последовательность чисел - путь алгоритма. Обратные пути считаются эквивалентными. Все рисунки сделаны автором в Microsoft PowerPoint.
Вправо и вниз
Идет обход по строкам, начиная с левой ячейки. Далее идет переход к следующей строке.
Вниз и вправо
Идет обход по столбцам, начиная с верхней ячейки. Далее идет переход к следующему столбцу.
Влево и вниз
Идет обход по строкам, начиная с правой ячейки. Далее идет переход к следующей строке.
Вверх и вправо
Идет обход по столбцам, начиная с нижней ячейки. Далее идет переход к следующему столбцу.
Вправо и вниз змейкой
Идет обход по строкам. Отсчет ведется с левой верхней ячейки. При переходе на следующую строку меняется направление.
От автора: Обходы ортогональной змейкой - практически готовый шаблон для одномаршрутного лабиринта, т.е. без петель и тупиков.
Влево и вниз змейкой
Идет обход по строкам. Отсчет ведется с правой верхней ячейки. При переходе на следующую строку меняется направление.
Вниз и вправо змейкой
Идет обход по стобцам. Отсчет ведется с левой верхней ячейки. При переходе на следующий столбец меняется направление.
Вверх и вправо змейкой
Идет обход по стобцам. Отсчет ведется с левой нижней ячейки. При переходе на следующий столбец меняется направление.
Вправо-вверх диагональю
Идет обход по диагоналям вправо и вверх. Отсчет начинается с левой верхней ячейки.
Влево-вниз диагональю
Идет обход по диагоналям влево и вниз. Отсчет начинается с левой верхней ячейки.
Влево-вверх диагональю
Идет обход по диагоналям влево и вверх. Отсчет начинается с левой нижней ячейки.
Вправо-вниз диагональю
Идет обход по диагоналям вправо и вниз. Отсчет начинается с левой нижней ячейки.
Вправо-вверх диагональной змейкой
Идет обход по диагоналям: сначала вправо и вверх, затем направление меняется на противоположное при переходе к следующей диагонали. Отсчет начинается с левой верхней ячейки.
Влево-вниз диагональной змейкой
Идет обход по диагоналям: сначала влево и вниз, затем направление меняется на противоположное при переходе к следующей диагонали. Отсчет начинается с левой верхней ячейки.
Влево-вверх диагональной змейкой
Идет обход по диагоналям: сначала влево и вверх, затем направление меняется на противоположное при переходе к следующей диагонали. Отсчет начинается с левой нижней ячейки.
Вправо-вниз диагональной змейкой
Идет обход по диагоналям: снчала вправо и вниз, затем направление меняется на противоположное при переходе к следующей диагонали. Отсчет начинается с левой нижней ячейки.
Спиралью по часовой, начиная с левой верхней
Идет обход по спирали, которая закручивается по часовой стрелке. Отсчет идет с левой верхней ячейки.
Спиралью по часовой, начиная с правой верхней
Идет обход по спирали, которая закручивается по часовой стрелке. Отсчет идет с правой верхней ячейки.
Спиралью по часовой, начиная с правой нижней
Идет обход по спирали, которая закручивается по часовой стрелке. Отсчет идет с правой нижней ячейки.
Спиралью по часовой, начиная с левой нижней
Идет обход по спирали, которая закручивается по часовой стрелке. Отсчет идет с левой нижней ячейки.
Спиралью против часовой, начиная с левой верхней
Идет обход по спирали, которая закручивается против часовой стрелки. Отсчет идет с левой верхней ячейки.
Спиралью против часовой, начиная с правой верхней
Идет обход по спирали, которая закручивается против часовой стрелки. Отсчет идет с правой верхней ячейки.
Спиралью против часовой, начиная с правой нижней
Идет обход по спирали, которая закручивается против часовой стрелки. Отсчет идет с правой нижней ячейки.
Спиралью против часовой, начиная с левой нижней
Идет обход по спирали, которая закручивается против часовой стрелки. Отсчет идет с левой нижней ячейки.
Вот такие основные алгоритмы, применяемые для обхода ячеек. Если вы знаете еще алгоритмы, применимые к прямоугольной сетке любой длины, пишите в комментариях.
P.S.
1. Я помню одну компьютерную игру, похожую на пазл и пятнашки. Там надо было передвигать фрагменты рисунка, но с одной особенностью: при перемещении другие фрагменты автоматически перемещались согласно определенному алгоритму обхода ячеек. Всего таких алгоритмов в игре было 10, включая 4 диагональных и 2 спиральных. Если вы знаете ту игру, скажите название или дайте ссылку для скачивания на Windows или Android.
2. В настоящее время в Германии продолжается строительство так называемой "Пирамиды времени" - конструкции из 120 столбов, которая на выходе должна напоминать пирамиду размерностью 8x8 в 4 этажа. в момент написания статьи уже поставлено 3 столба, в 2023 году планируется возведение 4-го. Попробуйте угадать, в каком порядке будут поставлены стобцы. Относительно каждого "слоя" - есть 3 варианта:
а) Вправо и вниз
б) Вправо и вниз змейкой
в) Спиралью по часовой, начиная с левой верхней
А по более "высоким столбам" - будут ли сначала столбы по одному слою ставить, или каждый "высокий столбец" (из 2 и более блоков) сразу?
