#include "rect.h"
using namespace std;
vector<vector<int>> v;
int n, m;
bool vs[2505][2505];
int cnt[2505][2505];
int minX[2505][2505];
int minY[2505][2505];
int maxX[2505][2505];
int maxY[2505][2505];
void dfs(int x, int y, int px, int py){
if(x < 0 || y < 0 || x >= n || y >= m) return;
if(v[x][y] == 1) return;
if(vs[x][y]) return;
vs[x][y] = true;
cnt[px][py]++;
minX[px][py] = min(minX[px][py], x);
maxX[px][py] = max(maxX[px][py], x);
minY[px][py] = min(minY[px][py], y);
maxY[px][py] = max(maxY[px][py], y);
dfs(x-1, y, px, py);
dfs(x, y-1, px, py);
dfs(x+1, y, px, py);
dfs(x, y+1, px, py);
return;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
v = a;
n = (int)a.size();
m = (int)a[0].size();
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
if(vs[i][j]) continue;
minX[i][j] = 1e9;
maxX[i][j] = -1;
minY[i][j] = 1e9;
maxY[i][j] = -1;
dfs(i, j, i, j);
}
}
long long res = 0;
for(int i=1; i<n-1; i++){
for(int j=1; j<m-1; j++){
if(cnt[i][j] == 0) continue;
if((maxX[i][j]-minX[i][j]+1)*(maxY[i][j]-minY[i][j]+1) != cnt[i][j]) continue;
if(minX[i][j] == 0 || maxX[i][j] == n-1 || minY[i][j] == 0 || maxY[i][j] == m-1) continue;
res++;
}
}
return res;
}
