#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
int S[2500][2500];
int H,W,res;
int calc(int lx,int rx,int ly,int ry){
return S[rx][ry]-(ly?S[rx][ly-1]:0)-(lx?S[lx-1][ry]:0)+((lx&&ly)?S[lx-1][ly-1]:0);
}
long long count_rectangles(vector<vector<int>>a){
H=a.size();
W=a[0].size();
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
S[i][j]+=a[i][j];
}
}
for(int i=0;i<H;i++){
for(int j=1;j<W;j++){
S[i][j]+=S[i][j-1];
}
}
for(int i=0;i<W;i++){
for(int j=1;j<H;j++){
S[j][i]+=S[j-1][i];
}
}
for(int i=1;i<H-1;i++){
for(int j=1;j<W-1;j++){
if(a[i-1][j]&&a[i][j-1]&&!a[i][j]){
int xr,yr;
for(yr=j;yr<W-1&&!a[i][yr];yr++);
yr--;
for(xr=i;xr<H-1&&!a[xr][j];xr++);
xr--;
if(calc(i,xr,j,yr)==0&&calc(i,xr,j-1,j-1)==xr-i+1&&calc(i,xr,yr+1,yr+1)==xr-i+1&&calc(i-1,i-1,j,yr)==yr-j+1&&calc(xr+1,xr+1,j,yr)==yr-j+1)res++;
j=yr;
}
}
}
return res;
}
