#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2503;
const int M = N * N;
const int di[] = {0, 0, 1, -1};
const int dj[] = {1, -1, 0, 0};
int n, m;
int p[M], sz[M];
int x[M], xx[M], y[M], yy[M];
int pref[N][N];
int get (int i, int j) {
return i * m + j;
}
int getSum (int i, int ii, int j, int jj) {
return pref[ii][jj] - pref[i - 1][jj] - pref[ii][j - 1] + pref[i - 1][j - 1];
}
int get (int v) {
return p[v] = (p[v] == v ? v : get(p[v]));
}
inline void unite (int u, int v) {
u = get(u); v = get(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
sz[v] += sz[u];
p[u] = v;
x[v] = min(x[v], x[u]);
xx[v] = max(xx[v], xx[u]);
y[v] = min(y[v], y[u]);
yy[v] = max(yy[v], yy[u]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = (int) a.size();
m = (int) a[0].size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int num = get(i, j);
p[num] = num;
sz[num] = 1;
x[num] = xx[num] = i;
y[num] = yy[num] = j;
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
}
for (int i = 1; i < n - 1; ++i) {
for (int j = 1; j < m - 1; ++j) {
if (a[i][j] == 0) {
for (int k = 0; k < 4; ++k) {
int ni = i + di[k], nj = j + dj[k];
if (a[ni][nj] == 0) {
unite(get(i, j), get(ni, nj));
}
}
}
}
}
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
for (int j = 1; j < m - 1; ++j) {
int num = get(i, j);
if (get(num) == num) {
if (x[num] > 0 && xx[num] < n - 1 && y[num] > 0 && yy[num] < m - 1) {
ans += getSum(x[num], xx[num], y[num], yy[num]) == 0;
}
}
}
}
return ans;
}
