#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
int n, m;
bool vis[2500][2500];
void dfs(int x, int y, map<int, int>& R, map<int, int>& C){
vis[x][y] = true;
R[x]++;
C[y]++;
if(x+1<n && !vis[x+1][y]) dfs(x+1, y,R,C);
if(x-1>=0 && !vis[x-1][y]) dfs(x-1, y,R,C);
if(y+1<m && !vis[x][y+1]) dfs(x, y+1, R,C);
if(y-1>=0 && !vis[x][y-1]) dfs(x, y-1,R,C);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
long long cnt = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
vis[i][j] = a[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(vis[i][j]) continue;
bool yes = true;
map<int,int>R,C;
dfs(i, j, R, C);
for(auto itr : R){
yes &= (itr.second == R.begin()->second);
}
for(auto itr : C){
yes &= (itr.second == C.begin()->second);
}
yes &= !R.count(0);
yes &= !R.count(n - 1);
yes &= !C.count(0);
yes &= !C.count(m - 1);
if(yes) cnt++;
}
}
return cnt;
}
