Block

时间限制: 1 Sec  内存限制: 128 MB

题目描述

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要压缩她的图片至少需要改变颜色的像素点的个数。

 

样例输入

复制样例数据

3 5
00100
10110
11001

样例输出

5

 

提示

选择k=2，图片被补全为，如下：
001000
101100
110010
000000
为使每个2×2的小块颜色一致，改变颜色为，如下：
001100
001100
000000
000000
可以发现这是所有情况中改变颜色的像素点数最少的，改变了5个像素点的颜色(答案为5的改色方案不止这一种)。

 

枚举选择的正方形的边长，然后记录每个中1和0的个数，如果1多，那么都改成1，否则改成0；

因为要求的是最小移动次数，当算法中间需要该的次数大于已有的ans，那么就不需要继续下去直接开始下一个。不优化超时。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m;
char s[2005][2005];
int a[2005][2005];

int slove(int x, int y, int len){
	int num = 0;
	for (int i = x; i < x + len; i++){
		for (int j = y; j < y + len; j++){
			if(a[i][j] == 1) num++;
		}
	}
	num = min(num, len * len - num);
	return num;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++){
		scanf("%s", s[i] + 1);
		for (int j = 1; j <= m; j++){
			a[i][j] = s[i][j] - '0';
		}
	}
	int N = max(n, m);// 最大化选择的边长
	int ans = 0x3f3f3f3f;
	for (int i = 2; i <= N; i++){
		int num = 0;
		for (int j = 1; j < n + i; j += i){
			for (int k = 1; k < m + i; k += i){
				num += slove(j, k, i);
				if(num > ans) break; // 一个小小的优化
			}
			if(num > ans) break;
		}
		ans = min(ans, num);
	}
	printf("%d\n", ans);

	return 0;
}
/**/