题目描述

有一个n×m的矩形框架，但其中有些边被删除了。qmqmqm想知道剩余部分中还有多少完整的正方形。只有当一个正方形的每一条边均被保留下来，这个正方形才是完整的。

输入格式

输入第一行包含两个正整数n,m。

之后n行，每行m−1个空格隔开的整数为0或1，表示横向边的存在情况。

之后n−1行，每行m个空格隔开的整数为0或1，表示竖向边的存在情况。

输出格式

输出一行一个整数表示剩余完整正方形的个数。

样例

样例输入

3 31 10 11 11 1 11 0 1

样例输出

2 预处理每个方格上边往右最多能延伸的长度，每个方格左边往下最多能延伸的长度

枚举每一个小方格作为正方形的左上角 从边长1开始扩展，扩展到不能在扩展 时间复杂度：O（n^3 / w）

#include
          
           #define N 1001using namespace std;int n,m;int trans[N][N],erect[N][N];int left[N][N],up[N][N];void init(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        for(int j=1;j
           
            =k && left[i][j]>=k )                {                    if(up[i+k][j]>=k && left[i][j+k]>=k) ans++;                    k++;                }            }    printf("%d",ans);}int main(){    init();    solve();}