UOJ Logo

NOI.AC

#98. flag

统计

旗帜

时间限制:1秒,内存限制:128MB

读入文件名:flag.in

输出文件名:flag.out

【题目描述】

双色旗在外国国旗中非常常见,我们现在要研究一类标准双色旗。

标准双色旗是这样定义的:

1、标准双色旗由两个长宽均相等且颜色不同的单色条带组成。

2、两个单色条带上下或左右拼接而成。

3、单色条带是指只包含同种颜色的长方形。

对于长和宽分别为$n$和$m$的旗帜,旗帜上每个$1*1$的小格内有一种颜色,用大写或小写字母表示。

如:

NOIp  
NOIq  
NOIr

就是一个$3*4$大小的旗帜,但它并不是标准双色旗。

而:

OOO  
OOO  
iii  
iii  

OOII  
OOII  
OOII  
OOII  
OOII  

Ac  

A  
A  
K  
K

则都是标准双色旗。

现在有一个$n*m$大小的旗帜,保证$n$和$m$中至少有一个偶数。这个旗帜可能不是标准双色旗,你可以改变旗帜上的若干格的颜色,使它变成一个标准双色旗,请问至少要对多少格的颜色进行改变。

【输入格式】

输入共$n+1$行。

第一行包含两个正整数$n$和$m$,表示旗帜的长和宽,输入用一个空格分隔。

接下来$n$行,每行$m$个字符,表示旗帜的颜色。字符仅由大小写字母组成。

【输出格式】

输出一行包含一个整数,表示至少要改变多少格。

【输入输出样例1】

flag.in

2 2

AA

AA

flag.out

2

【输入输出样例2】

flag.in

2 3

AAA

BBB

flag.out

0

【输入输出样例3】

flag.in

3 4

ABcd

ABef

aAgh

flag.out

8

【数据规模与约定】

对于前70%的数据,$1 \le n,m \le 100$;

对于100%的数据,$1 \le n,m \le 1000$。

【样例3解释】

AAcc  
AAcc  
AAcc  

AAdd  
AAdd  
AAdd  

AAee  
AAee  
AAee  

AAff  
AAff  
AAff  

AAgg  
AAgg  
AAgg  

AAhh  
AAhh  
AAhh  

以上改动方案均是最优的,都改变了8格。