Задача E. Сладкая симметрия ≡
| Автор: | И. Туфанов | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 50 |
Условие
У Алисы и Боба была коробка конфет. Коробка имеет прямоугольную форму и разбита на N × M квадратных ячеек (N по вертикали и M по горизонтали). В каждой ячейке изначально находилась конфета.
Боб незаметно от Алисы съел несколько конфет и теперь хочет
переложить оставшиеся симметрично относительно вертикальной оси симметрии коробки,
чтобы Алиса ничего не заподозрила.
Другими словами, конфеты в первом столбце должны быть
расположены так же, как и в последнем, во втором — как в предпоследнем и т.д.
Найдите минимальное количество перекладываний конфет,
необходимое для того, чтобы уложить их симметрично.
Формат входного файла
В первой строке входного файла содержатся числа N M. В последующих N строках содержится по M символов '.' или '#'. Точка обозначает пустую ячейку, решетка — ячейку, занятую конфетой.
На картинке приведен пример перекладывания конфеты для первого теста и обозначена ось симметрии.
Формат выходного файла
В выходной файл выведите единственное число — минимальное необходимое количество перекладываний, либо −1, если уложить конфеты симметричным образом невозможно.
Ограничения
1 ≤ N, M ≤ 50;
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|