#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2502;
int v[maxn][maxn], marc[maxn][maxn], ma_col[maxn*maxn], me_col[maxn*maxn], qtd[maxn*maxn], ma_lin[maxn*maxn], me_lin[maxn*maxn], n, m, pd[maxn*maxn];
int dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
bool in(int x, int y){
return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs(int x, int y, int c){
qtd[c]++;
marc[x][y]=c;
ma_col[c]=max(ma_col[c],y); me_col[c]=min(me_col[c],y);
ma_lin[c]=max(ma_lin[c],x); me_lin[c]=min(me_lin[c],x);
if(ma_lin[c]==n||me_lin[c]==1) pd[c]=0;
if(ma_col[c]==m||me_col[c]==1) pd[c]=0;
//cout << x << ' ' << y << " " << pd[c] << endl;
for(int i=0;i<4;i++){
int nx=x+dx[i], ny=y+dy[i];
if(in(nx,ny)&&v[nx][ny]&&marc[nx][ny]==0) dfs(nx,ny,c);
}
}
ll count_rectangles(vector<vector<int> > a){
n=a.size(), m=a[0].size();
memset(me_col,1,sizeof(me_col)); memset(me_lin,1,sizeof(me_lin));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
v[i+1][j+1]=a[i][j]^1;
int c=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(marc[i][j]==0&&v[i][j]){
pd[++c]++;
dfs(i,j,c);
}
}
}
ll resp=0;
for(int i=1;i<=c;i++) if((ma_col[i]-me_col[i]+1)*(ma_lin[i]-me_lin[i]+1)==qtd[i]&&pd[i]) resp++;
return resp;
}
