Рассмотрим задачу с экзамена по программированию Тинькофф образование на Java-разработчик (лето 2024).
Я не претендую на правильность и оптимальность решений. В статье хочу рассмотреть, в том числе для себя, различные аспекты связанные с заданием. А именно работа с многомерным массивом, поворот матрицы in-place, транспонирование, тестирование методов.
Описание задачи: В одной из предыдущих задач требовалось вывести перевернутую матрицу, теперь задача усложняется:
при этом поворот необходимо осуществлять in-place, т. е. без выделения дополнительной памяти. Для этого вместо результирующей матрицы необходимо вывести последовательность операций. За одну операцию можно обменять местами два элемента матрицы. Вам дана матрица n*n, а также указано, надо ли повернуть изображение по часовой R или против часовой L стрелки. Выведите последовательность операций, чтобы исходная матрица повернулась на 90 градусов в указанном направлении.
Заметьте, что не обязательно переставлять элементы в том порядке, в котором происходил бы поворот, главное чтобы в результате матрица соответствовала повороту на 90 градусов. Также необязательно, чтобы количество операций было минимальным, нужно только вписаться в ограничения.
Формат входных данных
Первая строка содержит одно натуральное число n (1 <= n <= 10³°) и указание направления поворота -символ R или L. Следующие n строк содержат описание матрицы, по n целых неотрицательных чисел, не превосходящих 10¹⁸.
Формат выходных данных
В первой строке выведите число k - необходимое количество операций, при этом это число не должно превосходить 7n². В последующих k строках выведите по две пары чисел - координаты (x1, y1) и (x2, y2) ячеек, между которыми необходимо обменять элементы матрицы.
Замечание. Обратите внимание, что нумерация строк и столбцов матрицы ведется с 0, а не с 1.
Примеры данных
Пример 1
Ввод: Вывод:
2 L 1
0 0 1 1 0 1
0 1
Пример 2
Ввод: Вывод:
3 R 3
0 1 0 1 0 1 2
1 0 0 0 0 2 0
4 3 0 1 0 2 1
Пример 3
Ввод: Вывод:
1 L 0
5
Одним из способов повернуть матрицу по часовой стрелке на 90 градусов in-place, без создания нового объекта матрицы является алгоритм состоящий из декомпозиции задачи на 2 этапа. Первый, это транспонирование матрицы, второй - замена столбцов транспонированной матрицы между собой симметрично центра. В результате мы получим искомую матрицу, элементы которой повернуты на 90 градусов. Для того, чтобы повернуть матрицу в обратную сторону, можно совершить вышеописанный алгоритм трижды. Аналогично возможно реализовать поворот на 180 градусов.
Другой способ, это последовательное перемещение элементов последовательно с одной стороны воображаемого квадрата матрицы на другую сторону по слоям. На каждом слое таких перемещений 4, так как 4 стороны. Слоев будет n/2. Это следует из того, что ширина стороны каждого слоя это n - 2i (где i номер слоя и 0 это внешний слой). из уравнения n - 2i = 0 получаем, что слоев i = n/2. Для хранения одного элемента на слой, а не каждого, сохраним первый и пойдем против часовой. В конце, после всех перезаписей элементов по кругу запишем элемент из временной переменной на его место. И так для каждой позиции в стороне/ширине матрицы.
Однако, в задаче требуется не реально перемещать элементы, а указать координаты ячейки принимающей и источника. Следовательно, нам нужно эти значения получить и посчитать количество перемещений. Непонятно только как учитывать запись временного значения. Исходя из примеров, нам показано учитывать только явные перемещения элементов между ячейками, из примера 3 следует что их 3, а не 4.. из примера 1 вообще следует, что перемещение учитывается только 1. Можно предположить, что нам предлагается сравнить значения, и если они равны перемещения не осуществлять… Однако в процессе перемещений значения могут изменяться и по идеи при другом алгоритме какие-то перемещения не нужны, но это уже мысли сюр).
Я все же буду учитывать запись четвертой итерации записи в ячейку временного значения из первой позиции, тк иначе вывод выглядит бредово.
Если не сравнивать значения, то на каждый слой у нас происходит 5 перезаписей с учетом записи во временную переменную и записи из нее. Следовательно, всего 5 * n/2 = операций. Это количество очевидно меньше требуемых 7 * n^2.
Ограничения: количество элементов, размер матрицы помещается в Integer, а вот значения в Long. Однако обратим внимание, для решения задачи нам это в принципе не важно, так как повернуть собственно матрицу нам не требуется, а задача состоит вывезти координаты ячеек.
В коде я все же реализую поворот матрицы, хоть и на результат это не влияет.
Реализованы помимо задачи транспонирование матрицы.
Использовал подходящую для этого случая функциональность как классы типа Record для хранения координат.