题目描述
某土拨鼠又双叒叕没做完作业,为了保全性命,他必须躲到教室里的桌子底下来躲避来自老师的毒打(滑稽)。教室里的桌子被排列成了的矩形。a[i][j]=1表示在(i,j)这个点有桌子。土拨鼠能藏身的矩阵符合以下三个标准:
- 该子矩形的四条边上没有空位;
- 子矩形中的空位数量与有桌子的位置的数量之差不超过1(不包括侧面的桌子);
- 子矩形的长度和宽度必须大于1。
问题来了,有多少子矩阵符合该要求这些要求。
输入描述
第一行输入两个整数n,m,分别表示矩形的长和宽;
接下来输入一个的矩阵表示教室内的桌子排列情况。
输出描述
输出一个整数表示符合要求的子矩阵个数。
样例
样例1
输入
4 4
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1输出
3说明:
在该矩形中有两个全是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); }