[SDOI2011] 打地鼠
2024年12月24日小于 1 分钟
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int m, n;
int a[MAXN + 5][MAXN + 5];
int aa[MAXN + 5][MAXN + 5];
bool check(int r, int c)
{
// 复制一份,然后开敲
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
aa[i][j] = a[i][j];
// 左上开始,遇到一个地鼠就敲
for (int i = 1; i + r - 1 <= m; i++)
for (int j = 1; j + c - 1 <= n; j++)
{
if (!aa[i][j])
continue;
int now = aa[i][j];
for (int x = i; x <= i + r - 1; x++)
for (int y = j; y <= j + c - 1; y++)
{
if (aa[x][y] < now)
return false;
aa[x][y] -= now;
}
}
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (aa[i][j])
return false;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> m >> n;
int sum = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
sum += a[i][j];
}
int ans = sum;
for (int r = 1; r <= m; r++)
for (int c = 1; c <= n; c++)
{
if (sum % (r * c))
continue;
if (check(r, c))
ans = min(ans, sum / (r * c));
}
cout << ans;
return 0;
}