问题 3862 --2.块(Block)

3862: 2.块(Block)

题目描述

  Alice得到了一张由n×m个黑白像素点组成的图片,她想要压缩这张图片。压缩图片的过程如下:
1. 首先,选择一个正整数k(k>1),将图片划分成若干个k×k的小块。如果n,m不能被k整除,用白色像素点在图片的右边或下面补全,使补全成n,m都能被k整除。
2. 由于压缩时每个k×k的小块必须颜色一致(即全黑或者全白),所以需要先改变某些像素点的颜色,然后再进行压缩。

在Alice可以自由的选择任意一个大于1的正整数k作为小块的边长的情况下,请你告诉Alice,她至少需要改变多少个像素点的颜色。

输入

输入的第一行包含两个由空格隔开的正整数n,m(2≤n,m≤1000),表示图片的尺寸。
接下来n行,每行包含一个长度为m的”01”串,表示Alice得到的那张图片。”0”表示一个白色像素点,”1”表示一个黑色像素点。

输出

输出一个整数,表示Alice要压缩她的图片至少需要改变颜色的像素点的个数。

样例输入输出

输入#1 复制
3 5
00100
10110
11001
输出#1 复制
5

提示

说明:
选择k=2,图片被补全为,如下:
001000
101100
110010
000000

为使每个2×2的小块颜色一致,改变颜色为,如下:

001100
001100
000000
000000

可以发现这是所有情况中改变颜色的像素点数最少的,改变了5个像素点的颜色(答案为5的改色方案不止这一种)。

【数据范围】
对于 40% 的数据,满足n=2或者m=2,且n,m≤100。
对于 70% 的数据,满足n,m≤100。
对于 100% 的数据,满足n,m≤1000。

序号 标题 作者 发表时间 费用 订购数 操作