暴力枚举第一个矩形的四条边，那么找出未覆盖部分的2的包围盒作为第二个矩形即可。
预处理二维前缀和来$O(1)$判断一个矩形内部是否有1，预处理前后缀坐标最值来$O(1)$得到包围盒。
时间复杂度$O(n^4)$。
#include<cstdio>
const int N=55,inf=10000;
int n,m,i,j,x,s[N][N],ans,A,B,C,D,S;
inline void umin(int&a,int b){a>b?(a=b):0;}
inline void umax(int&a,int b){a<b?(a=b):0;}
struct Info{
int xl,xr,yl,yr;
Info(){xl=yl=inf,xr=yr=0;}
void set(int x,int y){xl=xr=x,yl=yr=y;}
void operator+=(const Info&b){
umin(xl,b.xl);
umax(xr,b.xr);
umin(yl,b.yl);
umax(yr,b.yr);
}
}pre[N][N],suf[N][N],res,all;
inline int ask(int xl,int xr,int yl,int yr){return s[xr][yr]-s[xl-1][yr]-s[xr][yl-1]+s[xl-1][yl-1];}
int main(){
while(~scanf("%d%d",&n,&m)){
for(i=0;i<=n+1;i++)for(j=0;j<=m+1;j++)pre[i][j]=suf[i][j]=Info();
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
scanf("%d",&x);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
if(x==1)s[i][j]++;
if(x==2)pre[i][j].set(i,j),suf[i][j].set(i,j);
}
for(i=1;i<=n;i++)for(j=1;j<=m;j++)pre[i][j]+=pre[i-1][j],pre[i][j]+=pre[i][j-1];
all=pre[n][m];
if(all.xl>all.xr){
puts("0");
continue;
}
for(i=n;i;i--)for(j=m;j;j--)suf[i][j]+=suf[i+1][j],suf[i][j]+=suf[i][j+1];
ans=inf;
for(A=all.xl;A<=all.xr;A++)for(B=A;B<=all.xr;B++)for(C=all.yl;C<=all.yr;C++)for(D=C;D<=all.yr;D++){
if(ask(A,B,C,D))continue;
S=(B-A+1)*(D-C+1);
if(S>=ans)break;
res=pre[A-1][m];
res+=pre[n][C-1];
res+=suf[B+1][1];
res+=suf[1][D+1];
if(res.xl>res.xr){
ans=S;
continue;
}
if(ask(res.xl,res.xr,res.yl,res.yr))continue;
S+=(res.xr-res.xl+1)*(res.yr-res.yl+1);
umax(res.xl,A);
umin(res.xr,B);
umax(res.yl,C);
umin(res.yr,D);
if(res.xl<=res.xr&&res.yl<=res.yr)S-=(res.xr-res.xl+1)*(res.yr-res.yl+1);
umin(ans,S);
}
if(ans==inf)ans=-1;
printf("%d
",ans);
}
return 0;
}