题目大意

一堆桌子被排列成n×m（范围为[1,500]）的矩形，a[i][j]=1表示位置(i,j)处有桌子，0表示没有。我们要寻找满足这些条件的子矩形：

  1. 该子矩形的四条边上没有空位；
  2. 子矩形中的空位与桌子的数量之差不超过1（不包括侧面的桌子）；
  3. 子矩形的长度和宽度必须大于1。

有多少个子矩形可以满足要求？

解题思路

  • 500×500的矩阵，我们最多可以跑的算法。那么对付这样的枚举子矩阵题，我们的惯用套路就是用前缀和来维护了。我们在原矩阵中把0则当做-1，求出要求的0和1的差，记录前缀和。注意：前缀和不能算上边界的1。

  • 一种种查找的方法就是枚举上下行边界，再在每列查找。每个子矩阵要求四条边上都是1，所以我们枚举上下边界后，找一段在这两行都是1的列区间，再在这个区间里找。

  • 枚举每一列，如果这一列也都是1，就可以统计进去。那么每次找到合法的列，查询前面的前缀和是否有和它相差1以内的，计入答案。然后把自己的前缀和加入统计。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=25e4+10,M=510;
int a[M][M],b[M][M],f[N*2],s[M],n,m;
long long ans;
int main()
{
    int x,i,j,k,l;
    s[0]=N;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(!a[i][j]) a[i][j]=-1;
            b[i][j]=b[i-1][j]+a[i][j];
        }
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        {
            x=1;
            for(k=1;k<=m;k++)
            {
                if(a[i][k]!=1 || a[j][k]!=1)
                {
                    for(l=x;l<=k;l++)
                        if(b[j][l]-b[i-1][l]==j-i+1) f[s[l]]--;
                    x=k+1,s[k]=N;
                }
                else
                {
                    if(b[j][k]-b[i-1][k]==j-i+1)
                        ans+=f[s[k-1]]+f[s[k-1]+1]+f[s[k-1]-1];
                    s[k]=s[k-1]+b[j-1][k]-b[i][k];
                    if(b[j][k]-b[i-1][k]==j-i+1) f[s[k]]++;
                }
            }
            for(k=x;k<=m;k++)
                if(b[j][k]-b[i-1][k]==j-i+1) f[s[k]]--;
        }
    printf("%lld\n",ans);
}