ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC, Eastern subregion, Yekaterinburg, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Pharaohs’ Secrets

Time limit: 1.0 second
Memory limit: 64 MB
When programmer Alex was in Egypt, he not only swam in the Red Sea and went sightseeing, but also studied history. When Alex visited the place where an archeological dig of an ancient temple was carried out, an excavation worker complained to him that they had to drag very heavy statues from place to place every day. This was because some Egyptologist had read in an ancient papyrus that if the statues were arranged in a special order, then some ancient hiding-place would open. When the temple had been dug out, these statues had stood as soldiers, forming a rectangle. Some statues were identical, so there were several types of statues. They were to be arranged into a rectangle of the same dimensions on the same place with all rows and columns symmetric with respect to their middles. This meant that the statues standing in the same row or column at equal distances to its ends had to be of the same type.
Alex offered his help. He wants to find the way to transform the rectangle into a symmetric one by means of the minimal number of moves.


The first line contains the dimensions of the rectangle n and m (2 ≤ n, m ≤ 20). These integers are even. Each of the next n lines contains m lowercase English letters. Each letter denotes the type of the statue that stands in the rectangle at this position.


Output the minimal number of statues that should be moved in order to make a symmetric rectangle. It is guaranteed that this is possible.


4 4


The arrangement in the example can be transformed to a symmetric one in only two moves: first the statue of the type x from the upper row should be moved to the place in the rightmost column where there is the statue of the type b, and this statue then should moved to the place where the first statue stood. After all moves each place must be occupied by exactly one statue, but during the moving process there can be several statues at the same place.
Problem Author: Alex Gevak
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007
To submit the solution for this problem go to the Problem set: 1584. Pharaohs’ Secrets