#include "rect.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define fs first
#define sc second
vector<vector<int>> v,sz,l,r,u,d;
vector<vector<pair<int,int>>> pa;
pair<int,int> Find(int a,int b){
if(pa[a][b]==make_pair(a,b)){
return {a,b};
}
pair<int,int> p=Find(pa[a][b].fs,pa[a][b].sc);
return pa[a][b]=p;
}
void onion(pair<int,int> a,pair<int,int> b){
//cout<<"ok"<<endl;
a=Find(a.fs,a.sc),b=Find(b.fs,b.sc);
if(a==b){
return;
}
/*if(sz[a.fs][a.sc]>sz[b.fs][b.sc]){
swap(a,b);
}*/
sz[b.fs][b.sc]+=sz[a.fs][a.sc];
pa[a.fs][a.sc]=b;
l[b.fs][b.sc]=min(l[a.fs][a.sc],l[b.fs][b.sc]);
r[b.fs][b.sc]=max(r[a.fs][a.sc],r[b.fs][b.sc]);
u[b.fs][b.sc]=min(u[a.fs][a.sc],u[b.fs][b.sc]);
d[b.fs][b.sc]=max(d[a.fs][a.sc],d[b.fs][b.sc]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n=a.size();
int m=a[0].size();
v.resize(n+2,vector<int>(m+2,-1));
pa.resize(n+2,vector<pair<int,int>>(m+2));
sz.resize(n+2,vector<int>(m+2,1));
l=r=u=d=sz;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
v[i][j]=a[i-1][j-1];
pa[i][j]={i,j};
l[i][j]=r[i][j]=j;
u[i][j]=d[i][j]=i;
}
}
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
//cout<<i<<' '<<j<<endl;
for(int k=0;k<4;k++){
int i1=i+dx[k];
int j1=j+dy[k];
if(v[i][j]==0&&v[i1][j1]==0){
//cout<<i<<' '<<j<<' '<<i1<<' '<<j1<<endl;
onion(make_pair(i,j),make_pair(i1,j1));
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(v[i][j]==1){
continue;
}
if(make_pair(i,j)!=Find(i,j)){
continue;
}
if(u[i][j]==1||d[i][j]==n||l[i][j]==1||r[i][j]==m){
continue;
}
//cout<<i<<' '<<j<<endl;
int need=(r[i][j]-l[i][j]+1)*(d[i][j]-u[i][j]+1);
if(sz[i][j]==need){
ans++;
}
}
}
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
/*
5 5
0 0 1 1 0
0 1 1 1 1
0 1 0 0 1
0 1 0 0 1
0 1 1 1 1
*/
