原题链接：https://ac.nowcoder.com/acm/contest/5674/J

题目描述

某土拨鼠又双叒叕没做完作业，为了保全性命，他必须躲到教室里的桌子底下来躲避来自老师的毒打（滑稽）。教室里的桌子被排列成了的矩形。a[i][j]=1表示在(i,j)这个点有桌子。土拨鼠能藏身的矩阵符合以下三个标准：

1. 该子矩形的四条边上没有空位；
2. 子矩形中的空位数量与有桌子的位置的数量之差不超过1（不包括侧面的桌子）；
3. 子矩形的长度和宽度必须大于1。
   问题来了，有多少子矩阵符合该要求这些要求。

输入描述

第一行输入两个整数n,m，分别表示矩形的长和宽；
接下来输入一个的矩阵表示教室内的桌子排列情况。

输出描述

输出一个整数表示符合要求的子矩阵个数。

样例

1. 样例1

• 输入

  4 4
  1 1 1 1
  1 0 1 1
  1 1 0 1
  1 1 1 1

• 输出

  3

• 说明：

  在该矩形中有两个全是1的矩阵和该矩形本身符合要求。

2. 样例2

• 输入

  5 5
  1 0 1 1 1
  1 0 1 0 1
  1 1 0 1 1
  1 0 0 1 1
  1 1 1 1 1

• 输出

  3

题解思路

首先看到数据范围小的一批，全部枚举也只要枚举250000个点，所以是没问题的。
很容易想到，枚举矩阵，就先枚举左上角和右下角。但掐指一算，发现这个操作是，极容易超时。
那难道就没有暴力的方法了???
当然不会。（我说有就有）（滑稽）
前缀和应该不会使各位感到陌生，我们可以用前缀和来优化我们的暴力。
假设空位置的值为-1而非0，求每一列的前缀和，再枚举上下两条边，找到上下都是1的边，并判断是否为合法。
当然首先我们需要找到都是1的两列。
注意：判断时不要算上边上的1。

不要把[1,500]看成1,500(即英文中的1500)！！！

不要把[1,500]看成1,500(即英文中的1500)！！！

不要把[1,500]看成1,500(即英文中的1500)！！！

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=305,base=N*N;
int n,m,a[N][N],s[N][N],cnt[2*base];
ll ans=0;
int scp(int x,int y,int x2,int y2)
{
    return s[x2][y2]-s[x-1][y2]-s[x2][y-1]+s[x-1][y-1];
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,j,k,p;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]==1?1:-1);
        }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            if(a[i][k]&&a[j][k])
            {
                int l=k;
                while(l+1<=m&&a[i][l+1]&&a[j][l+1])l++;
                if(k==l)continue;  
                for(p=k;p<=l;p++)
                if(scp(i,p,j,p)==j-i+1)
                { 
                    int pre=scp(i+1,k+1,j-1,p-1)+base,now=scp(i+1,k+1,j-1,p)+base;   
                    ans+=cnt[pre-1]+cnt[pre]+cnt[pre+1];
                    cnt[now]++;
                }
                for(int p=k;p<=l;p++)
                    if(scp(i,p,j,p)==j-i+1)
                    {
                        int now=scp(i+1,k+1,j-1,p)+base;
                        cnt[now]--;
                    }  
                k=l+1; 
            }
        }
    printf("%lld\n",ans);
}