原题链接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的图片说明矩阵和该矩形本身符合要求。
  1. 样例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);
}