题解 | #最小面积子矩阵#

#include <bits/stdc++.h>
using namespace std;
int m,n,k;
int min_s=10001;
int mp[100][100];
/*mp:
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16
*/
void cal(int x,int y)
{
    int temp[m][n];
    //竖
    for(int i=x;i<m;i++)
    {
        temp[i][y]=mp[i][y];
        if(temp[i][y]>=k) min_s=min(min_s,1); 
    }
/*temp:(以x=0,y=0为例)
1  * * *
5  * * * 
9  * * *
13 * * * 
*/
    for(int i=x+1;i<m;i++)
    {
        temp[i][y]=temp[i-1][y]+mp[i][y];
        if(temp[i][y]>=k) min_s=min(min_s,i-x+1);
    }
/*temp:
1  * * *
6  * * * 
15 * * *
28 * * * 
*/
    //横
    for(int i=y;i<n;i++)
    {
        temp[x][i]=mp[x][i];
        if(temp[x][i]>=k) min_s=min(min_s,1);
    }
/*temp:
1 2 3 4
* * * * 
* * * *
* * * * 
*/
    for(int i=y+1;i<n;i++)
    {
        temp[x][i]=temp[x][i-1]+mp[x][i];
        if(temp[x][i]>=k) min_s=min(min_s,i-y+1);
    }
/*temp:
1 3 6 10
* * * * 
* * * *
* * * * 
*/
    for(int i=x+1;i<m;i++)
    {
        for(int j=y+1;j<n;j++)
        {//(x,y)是左上角，(i,j)是右下角
            temp[i][j]=temp[i-1][j]+temp[i][j-1]-temp[i-1][j-1]+mp[i][j];
            if(temp[i][j]>=k) min_s=min(min_s,(i-x+1)*(j-y+1)); 
        }
    }
}
int main() {
    while(cin>>m>>n>>k)
    {
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>mp[i][j];
            }
        }
        //以上是处理输入
        //接下来将每个坐标作为矩阵的左上角
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                cal(i,j);
            }
        }
        if(min_s==10001) cout<<"-1"<<endl;
        else cout<<min_s<<endl;
    }
}
// 64 位输出请用 printf("%lld")