#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
long long count_rectangles(vector<vector<int> > a) {
int N = a.size(),M = a[0].size();
vector<vector<bool>> vis(N,vector<bool>(M,false));
int li,ri,lj,rj;
int cnt;
int di[4] = {1,0,-1,0};
int dj[4] = {0,1,0,-1};
function<void(int,int)> fill_up = [&](int i,int j){
li = min(li,i), lj = min(lj,j);
ri = max(ri,i), rj = max(rj,j);
cnt++;
for(int d = 0;d < 4;d++){
int ni = i+di[d];
int nj = j+dj[d];
if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;
if(a[ni][nj] == 1) continue;
if(vis[ni][nj]) continue;
vis[ni][nj] = true;
fill_up(ni,nj);
}
};
long long ans = 0;
for(int i = 0;i < N;i++){
for(int j = 0;j < M;j++){
if(a[i][j] == 1 || vis[i][j]) continue;
li = i,ri = i,lj = j,rj = j,cnt = 0;
vis[i][j] = true;
fill_up(i,j);
if(li == 0 || lj == 0 || ri == N-1 || rj == M-1) continue;
if((ri-li+1)*(rj-lj+1) != cnt) continue;
// cout << i << " " << j << endl;
ans++;
}
}
return ans;
}
