P2484 [SDOI2011]打地鼠 暴力

题意：

给定一个\(n*m\)的矩阵，每个格子内有一定元素，你可以初始化一个\(r*c\)的矩阵，r和c自己定，每次操作可以刚好使\(r*c\)范围内的所有元素减少1,求最少多少次操作后矩阵刚好全部为0

范围&性质：\(1\le n,m \le 100\)

分析：

首先我们观察得到，对于最左上角的格子只有一种操作可以消除，同理每次消除后会形成新的左上角，所以对于固定的\(r\)和\(c\)，检验的复杂度是\(O(n^2)\)的，那么在枚举\(r\)和\(c\)，最终，整体复杂度为\(O(n^4)\)

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	
	int n,m,ans=2e9,sum;
	int a[105][105];
	
	bool check(int r,int c)
	{
		if(sum%(r*c)) return false;
		int b[105][105];
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				b[i][j]=a[i][j];
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(b[i][j])
				{
					int tmp=b[i][j];
					for(int p=1;p<=r;p++)
					{
						for(int q=1;q<=c;q++)
						{
							if(i+p-1>n||j+q-1>m) return false;
							b[i+p-1][j+q-1]-=tmp;
							if(b[i+p-1][j+q-1]<0) return false;
						}
					}
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(b[i][j]!=0) return false;
			}
		}
		return true;
	}
	
	void work()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				scanf("%d",&a[i][j]);
				sum+=a[i][j];
			}
		}
		for(int r=1;r<=n;r++)
		{
			for(int c=1;c<=m;c++)
			{
				if(check(r,c))
				{
					ans=min(ans,sum/(r*c));
				}
			}
		}
		printf("%d\n",ans);
	}
	
}

int main()
{
	zzc::work();
	return 0;
}