算法标签

• 矩形覆盖问题（Rectangle Covering）
• 前缀和优化（Prefix Sum Optimization）
• 暴力枚举（Brute Force Enumeration）

题意分析

给定一个 $N \times M$ 的矩阵，元素为 $0$, $1$ 或 $2$，且至少有一个 $2$。要求找到两个矩形（可重叠或相同），满足：

1. 所有 $2$ 必须被至少一个矩形覆盖；
2. 没有任何 $1$ 被这两个矩形覆盖；
3. 在满足条件的情况下，两个矩形的总面积最小。

若不存在解，输出 $-1$。

解题思路

1. 问题分解：

   • 统计所有 $2$ 的位置，确定其最小包围矩形（Bounding Box）。
   • 检查该包围矩形是否包含 $1$：若包含，则需分割为两个矩形。

2. 关键步骤：

   • 预处理：使用前缀和数组快速计算任意子矩阵中 $1$ 的数量。
   • 枚举分割方案：
     • 遍历所有可能的分割线（水平或垂直），将原包围矩形分为两个子矩形。
     • 确保两个子矩形覆盖所有 $2$，且不覆盖任何 $1$。
   • 面积计算：对每种有效分割方案，计算两个矩形的总面积，并记录最小值。

3. 数学表达：

   • 设包围矩形的边界为 $(x_{\text{min}}, y_{\text{min}})$ 到 $(x_{\text{max}}, y_{\text{max}})$。
   • 分割线位置 $(A, B, C, D)$ 需满足：$$\begin{cases} x_{\text{min}} \leq A \leq B \leq x_{\text{max}}, \\ y_{\text{min}} \leq C \leq D \leq y_{\text{max}}. \end{cases} $$
   • 检查条件：$$\text{Count}_1(\text{Rect}_1) = 0 \quad \text{且} \quad \text{Count}_1(\text{Rect}_2) = 0. $$

#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\n",ans);
  }
  return 0;
}