Осеннее палиндромище

Автор задачи и разработчик: Владислав Власов

Давайте сначала решим более простую задачу: сделать палиндромами все столбцы. Рассмотрим желаемую матрицу $$$s$$$, в ней $$$s_{1,1} = s_{n,1}$$$, $$$s_{1,2} = s_{n,2}$$$, ..., $$$s_{1,m} = s_{n,m}$$$. Получается, что первая строка должна совпадать с последней, аналогично вторая строка должна совпадать с предпоследней и так далее. Значит каждой строке должна сопоставляться такая же, кроме случая с нечётным $$$n$$$, тогда одна строка не может иметь пары; если более чем у одной строки нет пары, то палиндром составить невозможно.

Теперь соберём палиндром по столбцам. Воспользуемся двусторонней очередью и положим в неё строку без пары. Теперь будем класть в очередь парные: одну слева, другую справа. Для того, чтобы обрабатывать одинаковые строки вместе и в принципе знать количество вхождений каждой строки в матрицу, можно было воспользоваться ассоциативным массивом (unordered_map, HashMap, dict).

Заметим, что мы меняли местами только строки.

Теперь нам осталось сделать палиндромами строки матрицы. Давайте транспонируем её, то есть повернём на $$$90^{\circ}$$$. Теперь столбцы стали строками и наоборот. Значит на текущий момент каждая строка уже является палиндромом, и мы умеем делать палиндромами столбцы, не меняя порядок символов в строках, а меняя только строки местами.

Проделаем это снова, если хотя бы один раз было невозможно составить палиндром по столбцам, то ответ «NO». Время работы решения — $$$\mathcal{O}(nm)$$$.