#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <array>
using namespace std;
typedef long long ll;
const int maxn=2505, inf=1e9;
const int xp[]={0, 1, 0, -1};
const int yp[]={1, 0, -1, 0};
int n, m;
bool bio[maxn][maxn];
int v[maxn][maxn];
int maxx, maxy, minx, miny;
int br;
void dfs(int x, int y){
int xs, ys;
br++;
bio[x][y]=1;
maxx=max(maxx, x);
maxy=max(maxy, y);
minx=min(minx, x);
miny=min(miny, y);
for(int i=0; i<4; i++){
xs=x+xp[i];
ys=y+yp[i];
if(xs>-1 && ys>-1 && xs<n && ys<m && !bio[xs][ys] && !v[xs][ys]){
dfs(xs, ys);
}
}
}
ll count_rectangles(vector < vector < int > > a){
n=a.size();
m=a[0].size();
ll sol=0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
v[i][j]=a[i][j];
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!a[i][j] && !bio[i][j]){
maxx=0;
maxy=0;
minx=inf;
miny=inf;
br=0;
dfs(i, j);
// cout << minx << ' ' << maxx << ' ' << miny << ' ' << maxy << endl;
if(maxx==n-1 || maxy==m-1 || minx==0 || miny==0 || br!=(maxx-minx+1)*(maxy-miny+1)){
continue;
}
sol++;
}
}
}
return sol;
}
