#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 2500*2500;
int col[M], mn[M][2], mx[M][2];
vector<int> ver[M];
void add(int u,int v)
{
u=col[u], v=col[v];
if (u==v) return;
if (ver[u].size()<ver[v].size()) swap(u,v);
for (int i:ver[v])
col[i]=u, ver[u].push_back(i);
for (int j=0;j<2;j++)
mn[u][j]=min(mn[u][j],mn[v][j]),
mx[u][j]=max(mx[u][j],mx[v][j]);
ver[v].clear();
}
long long count_rectangles(vector<vector<int>> a)
{
int n=a.size(), m=a[0].size();
for (int i=1;i+1<n;i++)
for (int j=1;j+1<m;j++)
if (!a[i][j])
col[i*m+j]=i*m+j, mn[i*m+j][0]=mx[i*m+j][0]=i,
mn[i*m+j][1]=mx[i*m+j][1]=j, ver[i*m+j]={i*m+j};
for (int i=1;i+1<n;i++)
for (int j=1;j+1<m;j++)
{
if (a[i][j]) continue;
if (i>1 && !a[i-1][j]) add(i*m+j-m,i*m+j);
if (j>1 && !a[i][j-1]) add(i*m+j-1,i*m+j);
}
int ans=0;
for (int i=1;i<n-1;i++)
for (int j=1;j<m-1;j++)
if(col[i*m+j]==i*m+j)
{
int ar=(mx[i*m+j][0]-mn[i*m+j][0]+1)*(mx[i*m+j][1]-mn[i*m+j][1]+1);
if (ar==ver[i*m+j].size())
ans++;
}
return ans;
}
