Java(javac 1.8) 解法, 执行用时: 247ms, 内存消耗: 33124K, 提交时间: 2020-11-20 19:47:02

import java.util.Scanner;
import java.lang.Math;

public class Main{
    public static int check(int r,int c,int[][] map){
        int ans=0;
        int[][] cap=new int[map.length][map[0].length];
        
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[0].length;j++){
                cap[i][j]=map[i][j];
            }
        }
        
        for(int i=0;i<cap.length;i++){
            for(int j=0;j<cap[0].length;j++){
                if(cap[i][j]==0)continue;
                ans+=cap[i][j];
                int des=cap[i][j];
                for(int e=i;e<i+r;e++){
                    for(int k=j;k<j+c;k++){
                        if(e>=cap.length||k>=cap[0].length)return -1;
                        cap[e][k]-=des;
                        if(cap[e][k]<0)return -1;
                    }
                }
            }
        }
        return ans;
    }
    public static void main(String[] args){
        int m,n;
        Scanner scan=new Scanner(System.in);
        m=scan.nextInt();
        n=scan.nextInt();
        int[][] map=new int[m][n];
        int sum=0,maxm=-1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                map[i][j]=scan.nextInt();
                sum+=map[i][j];
                maxm=Math.max(maxm,map[i][j]);
            }
        }
        maxm=sum/maxm;
        int maxr=-1;
        int maxc=-1;
        int mins=sum+1;
        for(int i=1;i<=map.length;i++){
            if(check(i,1,map)>0){
                maxr=Math.max(maxr,i);
            }
        }
        for(int i=1;i<=map[0].length;i++){
            if(check(1,i,map)>0){
                maxc=Math.max(maxc,i);
            }
        }
        System.out.println(sum/(maxr*maxc));
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 30ms, 内存消耗: 460K, 提交时间: 2019-12-11 09:18:22

#include<bits/stdc++.h>
using namespace std;

int m,n,a[105][105],b[105][105],sum,ans=1e9;

int read()
{
	int r=0,f=1;char c=getchar();
	while((c<'0'||c>'9')&&(c^'-'))c=getchar();
	if(c=='-')f=-1,c=getchar();
	while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*f;
}

int main()
{
	m=read(),n=read();
	for(int i=1;i<=m;++i)
	for(int j=1;j<=n;++j)a[i][j]=read(),sum+=a[i][j];
	for(int r=1;r<=m;++r)
	for(int c=1;c<=n;++c)
	{
		if(sum%(r*c))continue;
		for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)b[i][j]=a[i][j];
		bool f=true;
		for(int i=1;i+r-1<=m;++i)
		{
			for(int j=1;j+c-1<=n;++j)
			{
				if(!b[i][j])continue;
				int x=b[i][j];
				for(int p1=i;p1<=i+r-1;++p1)
				{
					for(int p2=j;p2<=j+c-1;++p2)
					{
						b[p1][p2]-=x;
						if(b[p1][p2]<0)
						{
							f=false;
							break;
						}
					}
					if(!f)break;
				}
				if(!f)break;
			}
			if(!f)break;
		}
		if(f)ans=min(ans,sum/r/c);
	}
	printf("%d",ans);
	return 0;
}