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.
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