ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC, Восточный подрегион, Екатеринбург, октябрь 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Тайны фараонов

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Программист Алекс, отдыхая в Египте, не просто купался и смотрел на пирамиды, но и изучал историю. Труженик раскопок одного из древних храмов пожаловался Алексу, что их каждый день заставляют таскать с места на место тяжеленные статуи. Оказывается, какой-то египтолог вычитал в древнем папирусе, будто если статуи расставить нужным образом, то откроется какой-то древний тайник. Когда храм вскрыли, эти статуи стояли как солдаты в строю, образуя правильный прямоугольник. Некоторые статуи одинаковые, причем разных видов статуй меньше трех десятков. Их надо расставить в такой же строй, но так, чтобы каждый ряд и столбец прямоугольника стал симметричным, то есть, чтобы на одинаковых позициях от края стояли статуи одного вида.
Алекс вызвался помочь в перетаскивании статуй, и вычислить самый короткий способ превращения прямоугольника в симметричный. Помогите Алексу оценить количество перетаскиваний.

Исходные данные

В первой строке записаны четные числа n и m — размеры прямоугольника (2 ≤ n, m ≤ 20). В каждой из следующих n строк записано по m строчных латинских букв. Каждая буква обозначает некоторый тип статуй.

Результат

Выведите наименьшее количество перетаскиванеий статуй с места на место, чтобы получить симметричный строй. Гарантируется, что статуи всегда можно расставить должным образом.

Пример

исходные данныерезультат
4 4
abxa
xyyb
xyyx
abba
2

Замечания

Приведенное в примере расположение можно привести к симметричному виду всего за два перетаскивания: сначала взять статую вида x из самого верхнего ряда и перетащить ее в самый правый столбец, где стоит статуя вида b, а эту статую перетащить на прежнее место первой статуи (после всех перестановок каждое место в строю должно быть снова занято ровно одной статуей, хотя в процессе перетаскивания строй можно слегка потеснить).
Автор задачи: Алексей Жевак
Источник задачи: ACM ICPC 2007–2008. NEERC. Восточный подрегион. Екатеринбург, 27 октября 2007 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1584. Тайны фараонов